无向图找环(DFS)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6;
int cnt; //计数
int nums = 0;//计环
int e[N*2],ne[N*2],h[N],idx;
int vis[N],pre[N];
void add(int a,int b)
{
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int x,int fa)
{
vis[x] = 1;
for(int i = h[x];i!=-1;i=ne[i]){
int y = e[i];
if(y==fa)continue; //如果是无向的 a-->b 的同时也有 b-->a,所以直接排除另外的一种情况
if(vis[y]==0) //如果没有访问就标记当前元素的前一个元素
{
pre[y] = x;
dfs(y,x); //并且一直递归访问下去
}
else if(vis[y]==1)
{
int temp = x;
int count = 1;
while (temp!=y) //找路径
{
cout << temp << " ";
count++;//环中点的个数
temp = pre[temp];
}
cout << y << endl;
nums++; //环数+1
}
}
vis[x] = 2;//走过就不走了
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m,u,v; //n为点数 m为边数 u是起点v是终点
cin >> n >> m;
memset(h,-1,sizeof(h));
for(int i = 1;i <= m;i++)
{
cin >> u >> v;
add(u,v);
add(v,u);
}
for(int i = 1;i <= n;i++) //可能是非联通图
{
if(vis[i]==0) //每一次可以访问完和该点相连的所有点
{
dfs(i,-1);
}
}
cout << nums << endl; //环数
return 0;
}