并查集（1）-- 计算图中有几个连通分量和几个简单环

电玩女神 2022-07-15 08:30 54阅读 0赞

题目：[http://acm.hdu.edu.cn/showproblem.php?pid=3560][http_acm.hdu.edu.cn_showproblem.php_pid_3560]

HDU 3560 Graph’s Cycle

ComponentTime Limit: 2000/1000 MS (Java/Others)     Memory Limit: 131072/65536 K (Java/Others)

Total Submission(s): 674     Accepted Submission(s): 350  
  
  
Problem DescriptionIn graph theory, a cycle graph is an undirected graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain.  
Now, you are given a graph where some vertices are connected to be components, can you figure out how many components are there in the graph and how many of those components are cycle graphs.  
Two vertices belong to a same component if and only if those two vertices connect each other directly or indirectly.  
  
InputThe input consists of multiply test cases.   
The first line of each test case contains two integer, n (0 < n < 100000), m (0 <= m <= 300000), which are the number of vertices and the number of edges.  
The next m lines, each line consists of two integers, u, v, which means there is an edge between u and v.  
You can assume that there is no multiply edges and no loops.  
The last test case is followed by two zeros, which means the end of input.

Output

For each test case, output the number of all the components and the number of components which are cycle graphs.

Sample Input

8 9
    0 1
    1 3
    2 3
    0 2
    4 5
    5 7
    6 7
    4 6
    4 7
    2 1
    0 1
    0 0

Sample Output

2 1

1 0

代码：

#include<stdio.h>
    #include<string.h>
    int degree[100005],father[100005];
    char flag[100005];
    int Find(int i)
    { 
        int t=father[i]; 
        while(i!=father[i]) 
        { 
            i=father[i]; 
        } 
        father[t]=i; 
        return i;
    }
    void Union(int i,int j)
    { 
        int f1=Find(i),f2=Find(j); 
        if(f1!=f2) 
            father[f1]=f2;
    }
    
    int main()
    { 
        int i,n,m,s,s1,j,k; 
        while(scanf("%d%d",&n,&m)&&!(m==0&&n==0)) 
        { 
            memset(degree,0,sizeof(degree)); 
            memset(flag,1,sizeof(flag)); 
            for(i=0;i<n;i++) 
                father[i]=i; 
            for(i=0;i<m;i++) 
            { 
                scanf("%d%d",&j,&k); 
                degree[j]++; 
                degree[k]++; 
                Union(j,k); 
            } 
            // for(i=0;i<n;i++) 
            // printf("%d\n",father[i]); 
            s=s1=0; 
            for(i=0;i<n;i++) 
                if(degree[i]!=2)
                    flag[Find(i)]=0; 
            for(i=0;i<n;i++) 
            { 
                if(father[i]==i) 
                { 
                    s++; 
                    if(flag[i]==1) 
                        s1++; 
                } 
            } 
            printf("%d %d\n",s,s1); 
        } 
        return 0;
    }

注：Find（）函数的几种方法：

一、数据太大时会出现栈溢出  
int Find(int i)  
\{  
if(i!=father\[i\])  
farther\[i\]=Find(father\[i\]);  
return father\[i\];         //注意这里不是返回i  
\}

二、可能超时  
int Find(int i)  
\{  
while(i!=farther\[i\])  
   i=father\[i\];  
return i;  
\}

三、比较好  
int Find(int i)  
\{    
int t=father\[i\];  
while(i!=father\[i\])  
\{  
   i=father\[i\];  
\}  
father\[t\]=i;  
return i;  
\}

[http_acm.hdu.edu.cn_showproblem.php_pid_3560]: http://acm.hdu.edu.cn/showproblem.php?pid=3560