Training:并查集(最小生成树)

HDU 1213:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19354
给出人数和人的关系,认识的人可以在一桌,求最少要分几桌。简单并查集的应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
const int maxn=1010;
int p[maxn];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) p[fx]=fy;
return;
}
int main(){
int t;scanf("%d",&t);
while(t--){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) p[i]=i;
while(m--){
int a,b;scanf("%d%d",&a,&b);
if(find(a)!=find(b)) --n,merge(a,b);
}
printf("%d\n",n);
}
return 0;
}

HDU 1272:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11138
给出一个图中结点的关系,问是否是一个树。
判断只有一个连通分支,且边数 m = n − 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100010;
int p[maxn];
bool vis[maxn];
inline int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
int x,y;
bool flag=true;
for(int i=1;i<maxn;++i) p[i]=i;
while(~scanf("%d%d",&x,&y)){
if(x==-1&&y==-1) break;
if(!x&&!y){
if(flag){
int cnt=0;
for(int i=1;i<maxn;++i){
if(vis[i]&&p[i]==i) ++cnt;
if(cnt>1) {flag=false;break;}
}
}
puts(flag?"Yes":"No");
flag=true;
for(int i=1;i<maxn;++i) p[i]=i;
memset(vis,0,sizeof(vis));
continue;
}
if(!flag) continue;
vis[x]=vis[y]=true;
int fx=find(x),fy=find(y);
if(fx!=fy) p[fy]=fx;
else flag=false;
}
return 0;
}

HDU 1325:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=27465
与上题类似,是要判断是否为有向树。
在上题基础上还要满足每个结点的入度之多为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int p[maxn];
bool vis[maxn];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x!=y) p[y]=x;
return;
}
int main(){
int u,v,tt=0,edge=0,node=0;
bool flag=true;
for(int i=0;i<maxn;++i) p[i]=i;
while(~scanf("%d%d",&u,&v)){
if(u==-1&&v==-1) break;
if(!u&&!v){
if(node-1!=edge) flag=false;
printf("Case %d is %s tree.\n",++tt,flag?"a":"not a");
memset(vis,0,sizeof(vis));
for(int i=0;i<maxn;++i) p[i]=i;
flag=true;
node=edge=0;
}
if(!flag) continue;
if(!vis[u]) ++node,vis[u]=true;
if(!vis[v]) ++node,vis[v]=true;
++edge;
if(p[v]!=v) flag=false;
merge(u,v);
}
return 0;
}

HDU 1856:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=11137
给出 n 个人物关系,问最多能挑选出的有着直接或间接朋友关系的集合的人的数量。并查集初始化每个人的权值为一,求最大权值的集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int p[maxn],num[maxn];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) p[fx]=fy,num[fy]+=num[fx];
return;
}
int main(){
int n;
while(~scanf("%d",&n)){
if(!n){printf("1\n");continue;}
int ans=0,max_=0;
for(int i=1;i<maxn;++i) p[i]=i,num[i]=1;
for(int i=1;i<=n;++i){
int u,v;
scanf("%d%d",&u,&v);
max_=max(max_,u),max_=max(max_,v);
merge(u,v);
}
for(int i=1;i<=max_;++i) ans=max(ans,num[i]);
printf("%d\n",ans);
}
return 0;
}

HDU 1102:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18449
给出 n 个点之间任意两点建立通路的费用,再给出 m 条建好的路,求最小生成树(MST)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int g[110][110];
int p[maxn],u[maxn],v[maxn],w[maxn],r[maxn],b[maxn];
bool cmp(int i,int j){
return w[i]<w[j];
}
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
int n,m;
while(~scanf("%d",&n)){
m=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
scanf("%d",&w[m]);
u[m]=i,v[m]=j,r[m]=m,++m;
}
--m;
for(int i=1;i<=n;++i) p[i]=i;
int q;scanf("%d",&q);
for(int i=1;i<=q;++i){
int u,v;scanf("%d%d",&u,&v);
int x=find(u),y=find(v);
p[x]=y;
}
sort(r+1,r+m+1,cmp);
int ans=0;
for(int i=1;i<=m;++i){
if(b[r[i]]) continue;
int e=r[i],x=find(u[e]),y=find(v[e]);
if(x!=y) ans+=w[e],p[x]=y;
}
printf("%d\n",ans);
}
return 0;
}

HDU 1232:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19355
有 n 个结点, m 条边,求使所有结点连通还要建立至少几条边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int p[maxn];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)&&n){
int cnt=0;
for(int i=1;i<=n;++i) p[i]=i;
for(int i=0;i<m;++i){
int x,y;scanf("%d%d",&x,&y);
int fx=find(x),fy=find(y);
if(fx!=fy) p[fx]=fy,++cnt;
}
printf("%d\n",n-1-cnt);
}
return 0;
}

HDU 1233:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=20289
给出n个结点和每个结点间的距离,求使所有结点连通的边的长度和最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int p[maxn],u[maxn],v[maxn],w[maxn],r[maxn];
bool cmp(int i,int j){
return w[i]<w[j];
}
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
int n;
while(~scanf("%d",&n)&&n){
int m=n*(n-1)/2;
for(int i=1;i<=n;++i) p[i]=i;
for(int i=1;i<=m;++i) scanf("%d%d%d",&u[i],&v[i],&w[i]),r[i]=i;
sort(r+1,r+m+1,cmp);
int ans=0;
for(int i=1;i<=m;++i){
int e=r[i],x=find(u[e]),y=find(v[e]);
if(x!=y) ans+=w[e],p[x]=y;
}
printf("%d\n",ans);
}
return 0;
}

HDU 1875:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=15740
给出结点的坐标,求使所有结点连通的边的最小花费和。当距离 d < 10 或 d > 1000 时不能建立边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=10010;
int u[maxn],v[maxn],r[maxn],p[maxn];
double w[maxn];
struct node{
int x,y;
node(int x=0,int y=0):x(x),y(y){}
}a[110];
bool cmp(int i,int j){
return w[i]<w[j];
}
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
int m=1;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j){
u[m]=i,v[m]=j,w[m]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
if(w[m]>=10&&w[m]<=1000) ++m;
}
--m;
for(int i=1;i<=m;++i) r[i]=i;
for(int i=1;i<=n;++i) p[i]=i;
sort(r+1,r+m+1,cmp);
int cnt=0;
double ans=0;
for(int i=1;i<=m;++i){
int e=r[i],x=find(u[e]),y=find(v[e]);
if(x!=y) ans+=w[e],p[x]=y,++cnt;
}
if(cnt+1==n) printf("%.1lf\n",ans*100);
else printf("oh!\n");
}
return 0;
}

HDU 1879:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23262
给出结点、建造边的花费、部分已经建好的边,求使所有结点连通的最小花费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int p[maxn],u[maxn],v[maxn],w[maxn],r[maxn],b[maxn];
bool cmp(int i,int j){
return w[i]<w[j];
}
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
int n;
while(~scanf("%d",&n)&&n){
int m=n*(n-1)/2,ans=0;
for(int i=1;i<=n;++i) p[i]=i;
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&u[i],&v[i],&w[i],&b[i]),r[i]=i;
if(b[i]){
int x=find(u[i]),y=find(v[i]);
p[x]=y;
}
}
sort(r+1,r+m+1,cmp);
for(int i=1;i<=m;++i){
if(b[r[i]]) continue;
int e=r[i],x=find(u[e]),y=find(v[e]);
if(x!=y) ans+=w[e],p[x]=y;
}
printf("%d\n",ans);
}
return 0;
}

HDU 1811:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19357
给出一些人之间的偏序关系,问能否组成一张排名表。
首先用并查集储存相等的人,然后进行拓扑排序。如果出现一个以上的人不存在比自己大的人则为“UNCERTAIN”,如果形成环那么输出“CONFLICT”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100010;
char c[maxn];
int p[maxn],a[maxn],b[maxn],f[maxn];
vector<int> g[maxn];
queue<int> q;
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
int sum=n;
bool flag=true;
for(int i=0;i<n;++i) p[i]=i,f[i]=0,g[i].clear();
for(int i=0;i<m;++i){
scanf("%d %c %d",&a[i],&c[i],&b[i]);
if(c[i]=='='){
int x=find(a[i]),y=find(b[i]);
if(x!=y) p[y]=x,--sum;
}
}
for(int i=0;i<m;++i){
if(c[i]=='=') continue;
int x=find(a[i]),y=find(b[i]);
if(c[i]=='>') g[x].push_back(y),++f[y];
else g[y].push_back(x),++f[x];
}
while(!q.empty()) q.pop();
for(int i=0;i<n;++i)
if(!f[i]&&find(i)==i) q.push(i);
while(!q.empty()){
if(q.size()>1) flag=false;
int cur=q.front();q.pop();
--sum;
for(int i=0;i<g[cur].size();++i)
if(--f[g[cur][i]]==0) q.push(g[cur][i]);
}
if(sum>0) puts("CONFLICT");
else if(!flag) puts("UNCERTAIN");
else puts("OK");
}
return 0;
}

HDU 1829:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=16380
给出虫子的交配关系,问有没有同性恋的虫子。
用并查集合并,同时记录每个虫子所在的层数,出现相同层数的虫子交配即为同性恋。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
using namespace std;
const int maxn=20010;
int p[maxn],rank[maxn];
bool flag;
int find(int x){
if(x==p[x]) return p[x];
int t=find(p[x]);
rank[x]=(rank[p[x]]+rank[x])&1;
return p[x]=t;
}
void merge(int x, int y){
int a=find(x), b=find(y);
if(a==b){
if(rank[x]==rank[y]) flag=true;
return;
}
p[a]=b;
rank[a]=(rank[x]+rank[y]+1)&1;
}
int main(){
int t,tt=0;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d%d",&n,&m);
flag=false;
for(int i=0;i<=n;++i) p[i]=i,rank[i]=0;
for(int i=0;i<m;++i){
int x,y;scanf("%d%d",&x,&y);
if(flag) continue;
merge(x,y);
}
printf("Scenario #%d:\n",++tt);
printf("%s\n\n",flag?"Suspicious bugs found!":"No suspicious bugs found!");
}
return 0;
}

HDU 1198:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=16425
给出11种管道,再给出地图,问有几个连通分支。
貌似可以用并查集做,但是DFS时间也够,而且感觉DFS更加直观。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=55;
const int go[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
const bool road[11][4]={
{1,1,0,0},{0,1,1,0},{1,0,0,1},
{0,0,1,1},{0,1,0,1},{1,0,1,0},
{1,1,1,0},{1,1,0,1},{1,0,1,1},
{0,1,1,1},{1,1,1,1}
};
char g[maxn][maxn];
int vis[maxn][maxn];
int p[maxn],n,m;
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x!=y) p[y]=x;
return;
}
void dfs(int x,int y,int cnt){
char& c=g[x][y];
vis[x][y]=cnt;
for(int i=0;i<4;++i)
if(road[c-'A'][i]){
int a=x+go[i][0],b=y+go[i][1];
char& cc=g[a][b];
int j=0;
if(i==0) j=2;if(i==1) j=3;if(i==3) j=1;
if(road[cc-'A'][j]&&a>=0&&a<n&&b>=0&&b<m&&!vis[a][b])
dfs(a,b,cnt);
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
if(n==-1&&m==-1) break;
memset(vis,0,sizeof(vis));
int cnt=0;
for(int i=0;i<n;++i) scanf("%s",g[i]);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(!vis[i][j]) dfs(i,j,++cnt);
printf("%d\n",cnt);
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。

支付宝扫码领红包