首页 > 代码库 > UVALive 6091 - Trees (并查集)
UVALive 6091 - Trees (并查集)
题目链接: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 n500 and mn(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 (并查集)