• hdoj 1232 畅通工程


    Problem Description

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

    Input

    测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。
    注意:两个城市之间可以有多条道路相通,也就是说
    3 3
    1 2
    1 2
    2 1
    这种输入也是合法的
    当N为0时,输入结束,该用例不被处理。
     

    Output

    对每个测试用例,在1行里输出最少还需要建设的道路数目。
    咪乐|直播|盒子最新版 由于手机的泛载化,我们进入移动互联网时代。
    4 2
    1 3
    4 3
    3 3
    1 2
    1 3
    2 3
    5 2
    1 2
    3 5
    999 0
    0

    Sample Input

    1
    0
    2
    998

     这里用了并查集+路径压缩(理论上不需要路径压缩,但是为了更快,加上了)

     1 #include <string.h>
     2 #include <stdio.h>
     3 #include <algorithm>
     4 #include <math.h>
     5 #include <iostream>
     6 using namespace std;
     7 const int maxn=1000+5;
     8 int A[maxn],ran;
     9 
    10 void init(int n){
    11     for(int i=1;i<=n;i++) A[i]=i;
    12     ran=n;
    13 }
    14 
    15 int find(int x){
    16     int a=x;
    17     while(x!=A[x]){
    18         x=A[x];
    19     }
    20     while(a!=A[a]){ //路径压缩 
    21         int z=a;
    22         a=A[a];
    23         A[z]=x;
    24     }
    25     return x;
    26 }
    27 
    28 void Union(int u, int v){
    29     int a=find(u);
    30     int b=find(v);
    31     if(a!=b){
    32         A[a]=b;
    33         ran--;
    34     }
    35 }
    36 
    37 int main(){
    38     int n,m;
    39     while(scanf("%d",&n) && n!=0){
    40         scanf("%d",&m);
    41         int u,v;
    42         init(n);
    43         while(m--){
    44             scanf("%d%d",&u,&v);
    45             Union(u,v);
    46         }
    47         printf("%d
    ",ran-1);
    48     } 
    49     
    50     return 0;
    51     
    52 }
  • 相关阅读:
    聊一聊c++中指针为空的三种写法 ----->NULL, 0, nullptr
    HTML的教程网址
    c++构造函数谁先执行的问题
    从一个模板函数聊聊模板函数里面如何获得T的名字
    sourceInsight的技巧
    【java】实体类中 Set<对象> 按照对象的某个字段对set排序
    hibernate实体xml一对多关系映射
    layer父页面调用子页面的方法
    FreeMarker的<#if></#if>标签
    怎么把myeclipse项目导入IDEA中
  • 原文地址:https://www.cnblogs.com/z-712/p/15099910.html
走看看 - 开发者的网上家园
百度