美文网首页
2020-07-28 村村通

2020-07-28 村村通

作者: JalorOo | 来源:发表于2020-07-28 23:21 被阅读0次

    https://www.luogu.com.cn/problem/P1536

    #include <iostream>
    #include <cstdio>
    using namespace std;
    int f[1000001],ans=0;
    
    
    long long qmi(int m, int k)
    {
        int res = 1, t = m;
        while (k)
        {
            if (k&1) res = res * t;
            t = t * t;
            k >>= 1;
        }
        return res;
    }
    
    
    int read(){
        int x = 0,f = 1;
        char c = getchar();
        while (c<'0'||c>'9') {
            if (c=='-') {
                f = -1;
            }
            c = getchar();
        }
        while (c>='0'&&c<='9') {
            x = x*10+c-'0';
            c = getchar();
        }
        return x*f;
    }
    
    int find(int k){ //find函数 (寻找 "父亲")
        if(f[k]==k) return k;
        else return f[k]=find(f[k]);
    }
    
    void pin(int x,int y){ //进行连接的函数 (我为什么要写这个函数???)
        f[find(x)]=find(y);
    }
    
    int main()
    {
        int a,b;
        while(1){
            ans = 0; //答案de计数器
            a = read();
            if(a==0) return 0; //判断是否退出程序
            b = read();
            for(int i=1;i<=a;i++) f[i]=i; //初始化
            for(int i=1;i<=b;i++){
                int x = read(),y = read();
                pin(x,y); //连接提供的路径
            }
            //开始计算还需要的路径
            for(int i=1;i<a;i++){
                if(find(f[i])==find(f[i+1])){ //前后乡村联通 (好像要不要这句都无所谓)
                    continue;
                }else{ //如果前后乡村未联通
                    pin(i,i+1); //进行连接
                    ans++; //答案+1
                }
            }
            cout<<ans<<"\n"; //输出答案
        }
        return 0;
    }
    /*
    4 2
    1 3
    4 3
    3 3
    1 2
    1 3
    2 3
    5 2
    1 2
    3 5
    999 0
    0
    ============
    1
    0
    2
    998
    */
    

    相关文章

      网友评论

          本文标题:2020-07-28 村村通

          本文链接:https://www.haomeiwen.com/subject/wblcrktx.html