当前位置: 代码迷 >> 综合 >> UVa - 10227 - Forests ( 并查集 )
  详细解决方案

UVa - 10227 - Forests ( 并查集 )

热度:8   发布时间:2023-10-09 17:13:39.0

楼主英文不好,题目理解是个梗。。。。

题目不难,数据处理比较麻烦。


题目大意是:有 p 个人 , t 棵树 ,在森林中有书倒下,每个人听到自己感觉是某棵树倒下。

现在给出这些人的猜想。比如说编号为1 的人听到 2 ,3号树倒下,编号为2的人听到2号树倒下,编号为3的人听到2,3号树倒下,那么这三个人就有2种观点,一种观点是2,3号树倒下,一种是2号树倒下,题目就要求输出有几种观点。观点相同的人算一种观点。当两个人的猜想完全一致的时候,两个人的观点才算相同。

1.输入 n 代表有 n 组测试数据。

2.一个空行。

3.一些数据(有一些行,每行2个数字,第一个代表人的编号,第二个代表树的编号)

4.一个空行,

5.一些数据(。。。。。)

言外之意,每组数据中间有一个空行。


当输出数据的时候,同样每组结果中也要输出一个空行 。


麻烦点:给定组数后,每组数据中间用空行隔开,并没有告诉具体有多少行。这里楼主用了ungetc()函数,这个函数的作用是把读到的数据退回到输入流中。

如果读到回车或者输入结尾即EOF,说明当前组的数据输入完毕,如果不是的话,说明还输入数据,那么将数据退回到输入流中,重新读取。


#include<cstdio>
#include<cstring>#define N 105 
using namespace std;int f[N]; //节点 
int p_t[N][N]; //记录每个人听到的树 
int vis[N]; //记录是否听到过某树 //找到根节点 
int find(int x){return f[x] == x ? x : f[x] = find(f[x]);
} 
//合并集合 
void join(int x,int y){int fx = find(x);int fy = find(y);if(fx != fy) f[fx] = fy;
}//判断2人观点是否一致 
bool is_same(int p1,int p2,int t){for(int i=1 ;i<=t ;i++)if(p_t[p1][i]!=p_t[p2][i])return false;return true;
}int n,p,t,a,b,cnt; 
int main(){scanf("%d",&n);getchar(); while(n--){//初始化 cnt = 0;memset(vis,0,sizeof(vis));memset(sound,0,sizeof(sound));for(int i=0 ;i<N ;i++){f[i] = i;}//输入数据 scanf("%d%d",&p,&t);while(1){getchar(); char c = getchar();if(c != '\n' && c != EOF){ungetc(c,stdin); //不知道ungetc()的百度一下 scanf("%d%d",&a,&b);vis[a]=1;p_t[a][b] = 1;}else{break;}}//数据处理 合并集合 for(int i=1 ;i<=p ;i++){for(int j=i ;j<=p ;j++){if(vis[i]&&vis[j]){int fi = find(i);int fj = find(j);if((fi!=fj)&&(is_same(i,j,t))){join(fi,fj);}}}} //超找有几个集合 for(int i=0 ;i<=p ;i++){if(vis[i]&&(f[i]==i)){cnt++;} }//结果输出  printf("%d\n",cnt);if(n!=0)puts("");} return 0;
}