蓝桥杯2017年第八届真题-发现环 （C++代码）

解题思路:

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+5;

int pre[maxn];

int book[maxn];

int flag = 0;

vector<int>mp[maxn];

void init(int n)

{

for(int i = 1; i <= n; i++)

pre[i] = i;

return ;

}

int find(int x)

{

if(pre[x] == x) return x;

else return pre[x] = find(pre[x]);

}

void dfs(int st, int now)

{

//cout << st << " " << now << endl;

book[now] = 1;

for(int i = 0; i < mp[now].size(); i++)

{

int ed = mp[now][i];

//cout << now << "->" << ed <<endl;

if(ed == st) 

{

flag = 1; return ;

}

if(book[ed] != 1)

{

dfs(st, ed);

}

if(flag == 1) return ;

}

book[now] = 0;

return ;

}

int main()

{

int n;

scanf("%d", &n);

init(n);

for(int i = 0; i < n; i++)

{

int st, ed;

scanf("%d %d", &st, &ed);

mp[st].push_back(ed); mp[ed].push_back(st);

int tx = find(st);

int ty = find(ed);

if(tx != ty)

{

pre[tx] = ty;

}

else

{

dfs(st, st);

}

}



for(int i = 1; i <= n; i++)

{

if(book[i] == 1)

{

if(flag == 1)

{

printf("%d", i);

flag = 0;

}

else

{

printf(" %d",i);

}

}

}

return 0;

}