杭电1232 畅通工程

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

Problem Description



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


Input


测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。


注意:两个城市之间可以有多条道路相通,也就是说

3 3

1 2

1 2

2 1

这种输入也是合法的


当N为0时,输入结束,该用例不被处理。


Output


对每个测试用例,在1行里输出最少还需要建设的道路数目。


Sample Input


4 2

1 3

4 3

3 3

1 2

1 3

2 3

5 2

1 2

3 5

999 0

0


Sample Output


1

0

2

998


分析:并查集的简单应用,他问还需要建设多少条路径才能联通,也就是计算总共的最少道路-已经建设的道路。这里需要过滤的就是已经建设的道路是否有重复的情况,如果有重复的道路就不加1,判断是由有重复的关键就是判断两个点所在的树的根节点是否相同,如果相同,那么就不做任何操作,如果不同,将两棵树合并并且道路加一。


详细代码如下:(问题比较简单,没有考虑小数插大树,优化查找根节点等等)


import java.util.Scanner;
public class 杭电1232 {
  static int value=0;//表示当前已经连接的城镇数
  static int a[]=new int [1001];
  public static void main(String[] args) {    
    Scanner sc = new Scanner(System.in);         
        while(sc.hasNext())
        {
          int n=sc.nextInt();//城镇个数
          a=new int[n 1];
          if(n==0)break;
          int m=sc.nextInt();//道路个数
          for(int i=0;i<m;i  )
          {
            int a1=sc.nextInt();//两个城镇
            int a2=sc.nextInt();
            union(a1,a2);
          }
          System.out.println(n-1-value);        
          value=0;
        }
  }
  private static void union(int a1, int a2) {
    int q1=search(a1);
    int q2=search(a2);
      if(q1==q2){}//如果根相等,那么什么都不做
      else
      {
        value  ;
        a[q2]=q1;//a2指向a1先不考虑优化
        a[q1]--;
      }
  }
  private static int search(int a1) {
    if(a[a1]<=0) {return a1;}
    else
      return search(a[a1]);   
  } 
}


本人小白,复杂度和内存优化的都不够好。

目录
相关文章
|
6月前
|
Java 测试技术
HDU-1233-还是畅通工程
HDU-1233-还是畅通工程
35 0
|
Cloud Native
【刷题日记】417. 太平洋大西洋水流问题
本次刷题日记的第 45 篇,力扣题为:417. 太平洋大西洋水流问题 ,中等
|
测试技术
蓝桥杯2021年第十二届省赛真题-砝码称重(动态规划)
蓝桥杯2021年第十二届省赛真题-砝码称重(动态规划)
畅通工程 HDU - 1232
畅通工程 HDU - 1232
77 0
|
存储 机器学习/深度学习 算法
蓝桥杯十大常见天阶功法——虫之呼吸.贰之型.二分
蓝桥杯十大常见天阶功法——虫之呼吸.贰之型.二分
273 0
蓝桥杯十大常见天阶功法——虫之呼吸.贰之型.二分
|
算法
HDU - 2063: 过山车
HDU - 2063: 过山车
142 0
|
Java 测试技术
HDU 1232 畅通工程
畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 50540    Accepted Submission(s): 26968 Problem Description 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。
1021 0