P1330 封锁阳光大学 并查集解法 dfs解法

P1330 封锁阳光大学

题目描述

曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。

阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

有题可知：每条边的两个点不能同时选取，可以用黑白涂色来模拟，每相邻两点颜色不同，将黑色的点作为一个集合，白色作为另一个集合。当两点颜色相同时，之间仍有路时，输出Impossible。

图可能不是连通图，图中可能有多个子连通图，在每一个子连通图中，选择占点少的颜色让螃蟹占领。每一个子连通图中占点少的颜色累计即为答案。

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
#define maxm 100010
#define rep(i,a,b) for(int i=a;i<=b;i++)

int n,m;
int a[maxm],b[maxm];
int f[maxn*2];

int find(int x){
	return x==f[x] ? x : f[x]=find(f[x]) ;
}

void unity(int x,int y){
	x=find(x) , y=find(y) ;
	f[x]=y;
}


int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	cin>>n>>m;
	rep(i,1,2*n){//x为一种颜色， x+n为与x相反颜色 
		f[i]=i;
	}
	int x,y;
	rep(i,1,m){
		cin>>a[i]>>b[i];
		x=find(a[i]) , y=find(b[i]) ;
		if( x==y ){// a[i] b[i]是同一种颜色  
			cout<<"Impossible"<<endl ;
			return 0 ;
		}
		//同种颜色 并入同一个集合 
		unity(a[i],b[i]+n);//a[i]和(b[i]相反的颜色) 是同一种颜色 
		unity(a[i]+n,b[i]);	//a[i]相反的颜色 和b[i]是同一种颜色
	}
	
	
	int ans=0;
	int vis[maxn*2]={0};//标记
	rep(i,1,n){
		x=find(a[i]),y=find(b[i]);
		if(vis[x]||vis[y]) continue;//x，y之一被遍历过 证明该图被遍历过，寻找下一个分图 
		vis[x]=1,vis[y]=1;
		int ans1=0,ans2=0;
	    rep(j,1,n){
	    	//分别记下每个分图中两种颜色点个数 
		    if(find(j)==x) ans1++;
	    	else if(find(j)==y) ans2++;
    	}
    	ans+=min(ans1,ans2);//选数量少的颜色放螃蟹 
	}
	
	
	cout<<ans<<endl;
	return 0;
}

dfs解法：

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
#define maxm 100010

int n,m;
int a,b;
vector<int> g[maxn];
int vis[maxn];
int ans=0,ans1,ans2;
bool bo=true;
void dfs(int i,int color){
	
	for(int j=0;j<g[i].size();j++){
		a=g[i][j];
		if(vis[a]!=-1&&vis[a]==(color^1)) { cout<<"Impossible"<<endl; bo=false; exit(0);}//颜色冲突 
		if(vis[a]==color) continue;//已经涂过该色，跳过 
		if(vis[a]==-1){
			vis[a]=color;
			if(color==0)ans1++;//颜色计数 
			else ans2++;
			dfs(a,(color^1));//下个节点图相反颜色 
		}
	}
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=m;i++){//存图 
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	memset(vis,-1,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(vis[i]==-1){//没有涂色 
			ans1=0;
			ans2=1;
			vis[i]=1;//涂白 
			dfs(i,0);//下个点颜色为黑色 
			ans+=min(ans1,ans2);//取小 
		}
		
	}
	if(bo) cout<<ans<<endl;
	return 0;
}