首页 > 其他 > 详细

Luogu P1536 村村通

时间:2019-10-18 21:12:35      阅读:68      评论:0      收藏:0      [点我收藏+]

Luogu P1536 村村通

很简单的并查集。
记住\(道路数=区块数-1\)

#include<bits/stdc++.h>
#define N 1010

using namespace std;

int n,m,ans;
int fa[N];

int Find(int x) {
    return fa[x]==x?x:fa[x]=Find(fa[x]);
}

void Merge(int x,int y) {
    fa[Find(y)]=Find(x);
    return;
}

void Init() {
    for(int i=1;i<=n;i++) {
        fa[i]=i;
    }
    ans=0;
    return;
}

void Read() {
    scanf("%d",&m);
    for(int i=1;i<=m;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        Merge(u,v);
    }
    return;
}

void Solve() {
    for(int i=1;i<=n;i++) {
        if(fa[i]==i) {
            ans++;
        }
    }
    printf("%d\n",ans-1);
    return;
}

int main()
{
    while(scanf("%d",&n)&&n) {
        
        Init();
        Read();
        Solve();
    }
    return 0;
}

Luogu P1536 村村通

原文:https://www.cnblogs.com/luoshui-tianyi/p/11700722.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!