欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT 甲级 1118Birds in Forest (25分)

程序员文章站 2022-06-11 14:29:22
...

题目链接

A 1118

AC代码(C++)

不想用并查集,强行AC哈哈

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,q,k,id1,id2,cnt=1,num=0,max=0;
	scanf("%d",&n);
	vector<int> t(10001,0),p[n+1];
	while(n--)
	{
		scanf("%d",&k);
		vector<int> v(k),temp;
		for(int i=0;i<k;i++)
		{	
			scanf("%d",&v[i]);
			if(v[i]>max)
			{	max=v[i];	}
			if(t[v[i]]!=0)
			{	temp.push_back(t[v[i]]);	}	
		}
		if(temp.empty())
		{	
			for(int i=0;i<k;i++)
			{	
				p[cnt].push_back(v[i]);	
				t[v[i]]=cnt;
			}
			cnt++;
		}
		else
		{
			sort(temp.begin(),temp.end());
			int x=temp[0],y;
			for(int i=0;i<k;i++)
			{	
				p[x].push_back(v[i]);	
				t[v[i]]=x;
			}
			for(int i=1;i<temp.size();i++)
			{
				y=temp[i];
				for(int j=0;j<p[y].size();j++)
				{
					p[x].push_back(p[y][j]);
					t[p[y][j]]=x;
				}
				p[y].clear();
			}
		}	
	}
	for(int i=1;i<cnt;i++)
	{
		if(!p[i].empty())
		{	num++;	}
	}
	printf("%d %d\n",num,max);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d %d",&id1,&id2);
		if(t[id1]==t[id2]&&t[id1]!=0)
		{	printf("Yes\n");	}
		else
		{	printf("No\n");	}
	}
	return 0;
}

PAT 甲级 1118Birds in Forest (25分)

相关标签: 笔记 PAT