程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 1116 POI2008 CLO 並查集

BZOJ 1116 POI2008 CLO 並查集

編輯:C++入門知識

BZOJ 1116 POI2008 CLO 並查集


題目大意:給定一個無向圖,求能否找到一個點和邊的匹配,使匹配數為點數。

我又一次被並查集虐傻了。。。。

 

很好奇自信Dinic的話O(40W*√10W)的復雜度會不會T

估計會。。。

 

#include 
#include 
#include 
#include 
#define M 100100
using namespace std;
int n,m;
namespace Union_Find_Set{
	int fa[M];bool flag[M];
	int Find(int x)
	{
		if(!fa[x]||fa[x]==x)
			return fa[x]=x;
		return fa[x]=Find(fa[x]);
	}
	void Union(int x,int y)
	{
		x=Find(x);y=Find(y);
		if(x==y)
		{
			flag[x]=true;
			return ;
		}
		fa[x]=y;flag[y]|=flag[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(!flag[Find(i)])
		{
			puts("NIE");
			return 0;
		}
	puts("TAK");
	return 0;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved