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= 1=1且边数=0= 0=0，则为橡子。
复杂度分析
顶点数≤26\le 26≤26，边数有限。
代码实现
// The Forrest for the Trees// UVa ID: 599// Verdict: Accepted// Submission Date: 2016-08-12// UVa Run Time: 0.040s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=26;intparent[MAXN],ranks[MAXN];intfindSet(intx){return(x==parent[x]?x:parent[x]=findSet(parent[x]));}voidunionSet(intx,inty){x=findSet(x);y=findSet(y);if(x==y)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);intcases=stoi(line);for(inti=1;i<=cases;i++){memset(ranks,0,sizeof(ranks));memset(parent,-1,sizeof(parent));while(getline(cin,line),line.length()>0&&line.front()!='*'){intstart=-1,end=-1;for(intj=0;j<line.length();j++){if(isalpha(line[j])){if(start==-1)start=line[j]-'A';else{end=line[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(intj=0;j<line.length();j++)if(isalpha(line[j])){intvertex=line[j]-'A';if(parent[vertex]==-1)parent[vertex]=-2;}break;}inttrees=0,acorns=0;for(intj=0;j<26;j++)if(parent[j]==j)trees++;elseif(parent[j]==-2)acorns++;cout<<"There are "<<trees<<" tree(s) and "<<acorns<<" acorn(s).\n";}return0;}