用dfs判连通块和环

题目：给出一张图，判断有几个连通块（单点不算），有几个有环的连通块

判断连通块：
    方法一：dfs，若点在同一个连通块里，就标记一下
    方法二：并查集，判断有几个祖先
判断有无环（以后用方法一或三）：
    方法一：如果一个点除了走到它的父亲，还走到了一个被访问的点，说明有环
          （被访问的点说明一定存在一个已走过的路径到达该点）（以下代码是方法一）
    方法二：dfs或记度数，再判断是否是树（树的度数是n-1）
    方法三：并查集，如果一条边的两个点已经在同一个集合里，说明有环（类似kruskal）

//

#include<bits/stdc++.h>
using namespace std;
int const M=1e4+7;
int const N=1e3+7;
struct node{
    int a,next,len;
}e[M<<1];
int cnt,head[N];
void add(int x,int y,int len){
    e[++cnt].a=y;
    e[cnt].len=len;
    e[cnt].next=head[x];
    head[x]=cnt;
}
int t,n,m;
int vis[N];
int ans1=0,ans2=0,fg,fg2;
void dfs(int s,int fa,int z){
    vis[s]=1;
    for(int i=head[s];i;i=e[i].next){
        fg=1;
        if(e[i].a==fa) continue;
        if(vis[e[i].a]){
            if(fg2==0) fg2=1;
            continue;
        } 
        vis[e[i].a]=1;
        dfs(e[i].a,s,z);
    }
    if(fg) ans1=z+1;
}
int main(){
    cin >> t;
    for(int k=1;k<=t;++k){
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        memset(e,0,sizeof(e));
        cnt=0;
        ans1=0;ans2=0;
        cin >> n >> m;
        int a,b;
        for(int i=1;i<=m;++i){
            cin >> a >> b;
            add(a,b,1);add(b,a,1);
        }
        for(int i=1;i<=n;++i){
            fg=0;fg2=0;
            if(vis[i]) continue;
            dfs(i,i,ans1);
            if(fg2) ans2++;
        }
        cout << "Night sky #" << k << ": " << ans1;
        cout << " constellations, of which " << ans2;
        cout << " need to be fixed.\n\n";        
    }
    return 0;
}