HRBUST - 2026势力较量 -------HPU组队选拔赛（三）

淡淡的烟草味﹌ 2022-05-26 11:24 148阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td>势力较量</td> 
 </tr> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>Time Limit: 1000 MS</td> 
 <td>Memory Limit: 32768 K</td> 
 </tr> 
 </tbody> 
 </table> 
 <table> 
 <tbody> 
 <tr> 
 <td>Total Submit: 249(75 users)</td> 
 <td>Total Accepted: 104(67 users)</td> 
 <td>Rating: <img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""></td> 
 <td>Special Judge: No</td> 
 </tr> 
 </tbody> 
 </table></td> 
 </tr> 
 <tr> 
 <td>Description</td> 
 </tr> 
 <tr> 
 <td>在战火纷乱的古代有许多小国家。在这些小国家中，就会有一些强大的，一些弱小的。势力大的就会吞并势力小的， 形成更大的势力国家。现在给出你一些目前的国家势力关系，你能预算出以后的局势吗？ 为了简化问题，给每个国家编号，像“国家1”， “国家2”......“国家N” 国家的较量首先从人数上进行比较，人数多的能打赢人数少的。如果两个国家的人数相同，就根据国家头目的编号来判断， 我们假设编号大的国家能打得过编号小的国家。 当两个国家相遇的时候，就会有一场打斗，且一定要分出胜负，输的就会归顺于赢得, 形成一个新的国家。</td> 
 </tr> 
 <tr> 
 <td>Input</td> 
 </tr> 
 <tr> 
 <td>多组测试数据，处理到文件结束。对于每组数据： 第一行两个整数N，M。N为国家个数，M为关系数目。 接下来M行，每行两个整数u, v。表示国家u，国家v相遇，有一场打斗。 然后试一个整数Q，表示Q个询问。 接下来Q行，每行一个整数S。 (N&lt;100, M &lt; 100, Q &lt; 100)</td> 
 </tr> 
 <tr> 
 <td>Output</td> 
 </tr> 
 <tr> 
 <td>Case k: 对于每个询问，输出两个整数， 第一个整数表示S所在国家的头目，第二个整数表示S所在国家里边一共有多少个小国家。</td> 
 </tr> 
 <tr> 
 <td>Sample Input</td> 
 </tr> 
 <tr> 
 <td>5 3 1 2 1 3 4 5 2 1 5 5 4 1 2 1 3 1 4 1 5 4 2 3 4 5</td> 
 </tr> 
 <tr> 
 <td>Sample Output</td> 
 </tr> 
 <tr> 
 <td>Case 1: 2 3 5 2 Case 2: 2 5 2 5 2 5 2 5 </td> 
 </tr> 
 </tbody> 
</table>

本来以为能够一下写对的，但是没有考虑一些情况，导致我们队在这一道题上花费了很多时间，我写的代码也是基本上被重新推翻在写。

我的锅，一定要好好学习这部分，争取以后不在拉队伍的后腿

这一道题是并查集的题，初次看到以为是模板题，我就直接按着模板来敲了，但是做到最后发下模板并不能解决所有问题，想要解决这个问题得把模板变形，这就考验一个人对并查集理解的程度了，可能我对并查集这块儿只会用模板，而对自己思维的训练不够。

我希望下次再遇到这种问题的时候，队长让我优化代码的时候，我回答的不再是 我不会

/*
 	参考了我师父他们那一队的代码 
 */
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<cmath>
 using namespace std;
 
 const int maxn=1e3+3;
 
 int par[maxn];
 int a[maxn];//储存国家数 
 int b[maxn];
 
 void init(int n)
 {
 	for(int i=1;i<=n;i++)
 	{
 		par[i]=i;
 		a[i]=1;
 	}
 }
 
 int find(int x)
 {
 	return par[x]==x?x:par[x]=find(par[x]);
 }
 
 void join(int x,int y)
 {
 	par[x]=y;
 	a[y]+=a[x];
 }
 
 int main()
 {
 	int n,m,q;
 	int t=1;
 	while(~scanf("%d %d",&n,&m))
 	{
 		init(n);
 		for(int i=0;i<m;i++)
 		{
 			int x,y;
 			scanf("%d %d",&x,&y);
 			x=find(x);//直接对头目进行操作 
 			y=find(y);//
 			
 			if(x==y)	continue;
 			if(a[x]<a[y])	join(x,y);
 			if(a[y]<a[x])	join(y,x);
 			if(a[x]==a[y])
 			{
 				if(x<y)	join(x,y);
 				else	join(y,x);				
 			}			
 		}
 		
 		scanf("%d",&q);
 		for(int i=0;i<q;i++)	scanf("%d",&b[i]);
 		
 		printf("Case %d:\n",t++);
 		for(int i=0;i<q;i++)	
 			printf("%d %d\n",find(b[i]),a[find(b[i])]); 
 		
 	}
 	return 0;
 }