首页 > 代码库 > UVALive 6091 - Trees （并查集）

UVALive 6091 - Trees （并查集）

2024-07-13 03:05:28   213人阅读

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4102


----------------------------------------------------------------------------------------------------------------------------------------------------------
欢迎光临天资小屋害羞害羞害羞害羞：http://user.qzone.qq.com/593830943/main
----------------------------------------------------------------------------------------------------------------------------------------------------------

A graph consists of a set of vertices and edges between pairs of vertices. Two vertices are connected if there is a path (subset of edges) leading from one vertex to another, and a connected component is a maximal subset of vertices that are all connected to each other. A graph consists of one or more connected components.
A tree is a connected component without cycles, but it can also be characterized in other ways. For example, a tree consisting of nvertices has exactly n - 1 edges. Also, there is a unique path connecting any pair of vertices in a tree.
Given a graph, report the number of connected components that are also trees.
Input
The input consists of a number of cases. Each case starts with two non-negative integers n and m, satisfying n$ \le$500 and m$ \le$n(n - 1)/2. This is followed by m lines, each containing two integers specifying the two distinct vertices connected by an edge. No edge will be specified twice (or given again in a different order). The vertices are labelled 1 to n. The end of input is indicated by a line containing n= m =0.
Output
For each case, print one of the following lines depending on how many different connected components are trees (T > 1 below):

Case x: A forest of T trees. 
Case x: There is one tree. 
Case x: No trees.

x is the case number (starting from 1).
Sample Input
6 3
1 2
2 3
3 4
6 5
1 2
2 3
3 4
4 5
5 6
6 6
1 2
2 3
1 3
4 5
5 6
6 4
0 0

Sample Output
Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.

题意：寻找有几棵树，要特别注意有多个环的情况；
代码如下：
#include<cstdio>
int father[1017];
int c[1017];//记录是否循环
int a, b, n, m, k;
int i, j;
int find(int x)
{
    return x==father[x]?x:father[x]=find(father[x]);
}
void Union(int x,int y)
{
	int f1=find(x);
	int f2=find(y);
	if(c[f1] && c[f2])//无效输入
		return ;
	k--;
	if(f1 != f2)
	{
		if(c[f2])//有环的作为父亲
			father[f1] = f2;
		else
			father[f2] = f1;
	}
	
	else if(f1 == f2)//标记
	{
		c[f1] = 1;
	}
}
void init()
{
	for(i = 1 ; i <=n ; i++ )
	{
		father[i] = i ;
		c[i] = 0;
	}
}
int main()
{
	int cas = 0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
		if(n == 0 && m == 0)
			break;
		init();
        k=n;
        for(i = 1; i <= m; i++ )
        {
            scanf("%d%d",&a,&b);
			Union(a,b);
        }
		if(k > 1)
			printf("Case %d: A forest of %d trees.\n",++cas,k);
		else if(k == 1)
		{
			printf("Case %d: There is one tree.\n",++cas);
		}
		else
		{
			printf("Case %d: No trees.\n",++cas);
		}
    }
    return 0 ;
}


UVALive 6091 - Trees （并查集）






























        

            
                
                  
                
                

                    联系

                    我们