Training：并查集（最小生成树）

发表于 分类于 Disqus：

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博客，格式可能有所偏差。 **

相关文章