题目描述

题目要求统计给定森林中的树和“橡子”的数量。森林由若干连通分量组成，每个连通分量若是一棵树（无环）则计为树，若只有一个孤立节点（无边）则计为橡子。

输入格式

第一行一个整数nnn，表示测试用例数。每个测试用例包含两部分：

1. 若干行边，每行格式为(A,B)，以一行*结束。
2. 一行顶点列表，格式为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;}