HDU 3560 並查集 Graph’s Cycle Component

分析: 這題另外還要求簡單環的個數, 只要加一個標記數組將不是簡單環的集合標記即可.

[cpp] 
#include<iostream>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<cstdio>  
#include<cmath>  
#include<iomanip>  
 
using namespace std; 
const int maxn=100000; 
int f[maxn]; 
int ds[maxn]; 
bool vis[maxn]; 
 
int find_set(int x){ 
    if(f[x]!=x)f[x]=find_set(f[x]); 
    return f[x]; 
} 
void union_set(int x,int y){ 
    x=find_set(x); 
    y=find_set(y); 
    if(x!=y)f[y]=x; 
} 
int main() { 
    int n,m; 
    while(~scanf("%d%d",&n,&m),n||m){ 
        memset(ds,0,sizeof(ds)); 
        memset(vis,true,sizeof(vis)); 
        for(int i=0;i<n;++i)f[i]=i; 
        while(m--){ 
            int a,b; scanf("%d%d",&a,&b); 
            ds[a]++; ds[b]++; 
            union_set(a,b); 
        } 
        for(int i=0;i<n;++i) 
            if(ds[i]!=2) vis[find_set(i)]=false; 
        int s=0,h=0; 
        for(int i=0;i<n;++i) 
            if(find_set(i)==i){ 
                s++; 
                if(vis[i])h++; 
            } 
        printf("%d %d\n",s,h); 
    } 
    return 0; 
} 

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>

using namespace std;
const int maxn=100000;
int f[maxn];
int ds[maxn];
bool vis[maxn];

int find_set(int x){
    if(f[x]!=x)f[x]=find_set(f[x]);
    return f[x];
}
void union_set(int x,int y){
    x=find_set(x);
    y=find_set(y);
    if(x!=y)f[y]=x;
}
int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m),n||m){
        memset(ds,0,sizeof(ds));
        memset(vis,true,sizeof(vis));
        for(int i=0;i<n;++i)f[i]=i;
        while(m--){
            int a,b; scanf("%d%d",&a,&b);
            ds[a]++; ds[b]++;
            union_set(a,b);
        }
        for(int i=0;i<n;++i)
            if(ds[i]!=2) vis[find_set(i)]=false;
        int s=0,h=0;
        for(int i=0;i<n;++i)
            if(find_set(i)==i){
                s++;
                if(vis[i])h++;
            }
        printf("%d %d\n",s,h);
    }
    return 0;
}