BZOJ 2079 Poi2010 Guilds 並查集

BZOJ 2079 Poi2010 Guilds 並查集

題目大意：給定一個無向圖，要求將一些點紅黑染色，使每個點及其相連的點中至少有一個黑色的點和一個紅色的點

逗比題ぽい~

對於任意一個大小>=2的連通圖，我們只需要搞出這個圖的任意一棵生成樹，將這棵生成樹撸成二分圖再染色就一定能滿足要求的ぽい~

因此無法滿足要求當且僅當存在一個大小為1的聯通塊ぽい~

並查集即可ぽい~

#include 
#include 
#include 
#include 
#define M 200200
using namespace std;
int n,m;
namespace Union_Find_Set{
	int fa[M],size[M];
	int Find(int x)
	{
		if(!fa[x])
			fa[x]=x,size[x]=1;
		if(fa[x]==x)
			return x;
		return fa[x]=Find(fa[x]);
	}
	void Union(int x,int y)
	{
		x=Find(x);y=Find(y);
		if(x==y) return ;
		fa[x]=y;size[y]+=size[x];
	}
}
int main()
{
	using namespace Union_Find_Set;
	int i,x,y;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		Union(x,y);
	}
	for(i=1;i<=n;i++)
		if(size[Find(i)]==1)
			return cout<<"NIE"<