P2839 畅通工程

朴灿烈づ我的快乐病毒、 2021-12-24 15:43 169阅读 0赞

# P2839 畅通工程 #

## 题目描述 ##

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

## 输入输出格式 ##

输入格式：

第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M

随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号

### 注意：两个城市连接多条公路是合法的 ###

输出格式：

至少还需建立多少条路

## 输入输出样例 ##

输入样例\#1：

3 3
    1 2
    1 3
    2 3

输出样例\#1：

输入样例\#2：

3 3
    1 2
    1 2
    2 1

输出样例\#2：

## 说明 ##

对于30%的数据，1<=N<=10

对于70%的数据，1<=N<=200

对于100%的数据，1<=N<=1000，1<=M<=1000

跟上一个题似乎是一样的

#include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define N 5100
    using namespace std;
    int fa[N];
    int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1; ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
        return x*f;
    }
    int find(int x)
    {
        if(x==fa[x]) return x;
        fa[x]=find(fa[x]);
        return fa[x];
    }
    int main()
    {
        int n,m,x,y,fx,fy,ans=0;
        n=read(),m=read();
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=m;i++)
        {
            x=read(),y=read();
            fx=find(x),fy=find(y);
            if(fa[fx]==fa[fy]) continue;
            fa[fx]=fy;
        }
        for(int i=1;i<=n;i++)
         if(fa[i]==i) ans++;
        printf("%d",ans-1);
        return 0;
    }

转载于:https://www.cnblogs.com/z360/p/7436484.html