[洛谷]P1330 封锁阳光大学 (#并查集 )

69 阅读 0 评论 46 点赞

我是靠谱客的博主寂寞钢笔，最近开发中收集的这篇文章主要介绍[洛谷]P1330 封锁阳光大学 (#并查集 )，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

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

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

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

输入格式

第一行：两个整数N，M

接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。

输出格式

仅一行：如果河蟹无法封锁所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。

输入输出样例

输入 #1复制

输出 #1复制

Impossible

输入 #2复制

3 2
1 2
2 3

输出 #2复制

说明/提示

【数据规模】

1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。

思路

有一个由n个结点构成的有m条边的图，需要在某几个点上放置河蟹，河蟹会占领该点上的所有边，相邻的河蟹之间会发生冲突，目的要让河蟹占领整个图。

我用的并查集，具体做法是把一张图分层，有点类似于bfs。一个合理的图不会出现同一层之间互相连接的边。这种图叫做分层图。

如果分层后，同一层两点之间有边相连，就可以判定不行。

河蟹直接不能相邻，那么我们只要让河蟹占据奇数层或者偶数层的所有点，不就ok？那么我们可以用并查集维护每一层。并查集的作用是使某些点具有相同的祖宗结点，那么他们直接就属于一个集合。同理，让奇数层的点属于同一个集合，偶数点属于同一集合，有点类似于关押罪犯。

#include <stdio.h>
#include <iostream>
#include <memory.h>
using namespace std;
int n,m,s1,s2,fa[100001]/*每个节点的祖宗是谁*/,e[100001][2]/*记录图信息*/
bool vis[100001];
int getfind(int v)//认爹函数
{
if(fa[v]==v)//祖宗节点是自己
{
return v;
}
else//继续认爹
{
fa[v]=getfind(fa[v]);
return fa[v];
}
}
inline void merge(int v,int u)//合并
{
register int t1,t2;
t1=getfind(v);//找他们的祖宗节点
t2=getfind(u);
if(t1!=t2)//不相同，就合并集合
{
fa[t2]=t1;
}
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
register int i,j;
cin>>n>>m;
for(i=1;i<=n*2;i++)
{
fa[i]=i;
}
for(i=1;i<=m;i++)
{
cin>>e[i][0]>>e[i][1];
int t1(getfind(e[i][0])),t2(getfind(e[i][1]));//先找祖先
if(t1==t2)//祖先一样，且他们在同一层
{
cout<<"Impossible"<<endl;
return 0;
}
else
{
merge(e[i][0]+n,e[i][1]);
merge(e[i][0],e[i][1]+n);
}
}
memset(vis,1,sizeof(vis));//以i为根节点的图是否放置和谐
int s(0);
for(i=1;i<=m;i++)
{
int t1(getfind(e[i][0])),t2(getfind(e[i][1]));
if(vis[t1]==1 && vis[t2]==1)//如果没有
{
vis[t1]=0;
vis[t2]=0;
s1=s2=0;
for(j=1;j<=n;j++)//在改分层图进行遍历找最佳答案
{
if(getfind(j)==t1) s1++;
else if(getfind(j)==t2) s2++;
}
s+=min(s1,s2);
}
}
cout<<s<<endl;
return 0;
}