UVa 599 The Forrest for the Trees

题目描述题目要求统计给定森林中的树和“橡子”的数量。森林由若干连通分量组成每个连通分量若是一棵树无环则计为树若只有一个孤立节点无边则计为橡子。输入格式第一行一个整数nnn表示测试用例数。每个测试用例包含两部分若干行边每行格式为(A,B)以一行*结束。一行顶点列表格式为A,B,C,...。输出格式对于每个测试用例输出一行There are x tree(s) and y acorn(s).。样例输入2 (A,B) (B,C) (B,D) (D,E) (E,F) (B,G) (G,H) (G,I) (J,K) (K,L) (K,M) **** A,B,C,D,E,F,G,H,I,J,K,L,M,N (A,B) (A,C) (C,F) ** A,B,C,D,F输出There are 2 tree(s) and 1 acorn(s). There are 1 tree(s) and 1 acorn(s).题目分析本题的核心是使用并查集Union-Find\texttt{Union-Find}Union-Find统计连通分量并判断每个分量是否为树。算法对于每条边将两个顶点合并。统计每个连通分量的顶点数和边数。若边数 顶点数−1- 1−1则为树若顶点数1 11且边数0 00则为橡子。复杂度分析顶点数≤26\le 26≤26边数有限。代码实现// The Forrest for the Trees// UVa ID: 599// Verdict: Accepted// Submission Date: 2016-08-12// UVa Run Time: 0.040s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN26;intparent[MAXN],ranks[MAXN];intfindSet(intx){return(xparent[x]?x:parent[x]findSet(parent[x]));}voidunionSet(intx,inty){xfindSet(x);yfindSet(y);if(xy)return;if(ranks[x]ranks[y])parent[y]x;else{parent[x]y;if(ranks[x]ranks[y])ranks[y];}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcasesstoi(line);for(inti1;icases;i){memset(ranks,0,sizeof(ranks));memset(parent,-1,sizeof(parent));while(getline(cin,line),line.length()0line.front()!*){intstart-1,end-1;for(intj0;jline.length();j){if(isalpha(line[j])){if(start-1)startline[j]-A;else{endline[j]-A;break;}}}if(parent[start]-1)parent[start]start;if(parent[end]-1)parent[end]end;unionSet(start,end);}while(getline(cin,line)){if(line.length()0)continue;for(intj0;jline.length();j)if(isalpha(line[j])){intvertexline[j]-A;if(parent[vertex]-1)parent[vertex]-2;}break;}inttrees0,acorns0;for(intj0;j26;j)if(parent[j]j)trees;elseif(parent[j]-2)acorns;coutThere are trees tree(s) and acorns acorn(s).\n;}return0;}