畅通工程

[编程题]畅通工程

热度指数：12944 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

输出

算法知识视频讲解

Java

秃头肥牛

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N;
        while (scanner.hasNext() && (N = scanner.nextInt()) != 0) {
            int M = scanner.nextInt();
            UnionFindSet ufs = new UnionFindSet(N, 1000);
            for (int i = 0; i < M; i++) {
                ufs.union(scanner.nextInt(), scanner.nextInt());
            }
            int count = -1;
            for (int i = 1; i <= N; i++) {
                if (ufs.father[i] == i) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
    public static class UnionFindSet {
        private int father[];
        private int height[];
        public UnionFindSet(int n, int max) {
            this.father = new int[max];
            this.height = new int[max];
            for (int i = 1; i <= n; i++) {
                this.father[i] = i;
                this.height[i] = 0;
            }
        }

        int find(int x) {
            if (x != father[x]) {
                father[x] = find(father[x]);
            }
            return father[x];
        }

        void union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                if (height[x] < height[y]) {
                    father[x] = y;
                } else if (height[x] > height[y]) {
                    father[y] = x;
                } else {
                    father[y] = x;
                    height[x]++;
                }
            }
        }
    }
}

发表于 2023-02-11 19:21:41 回复(0)

Java

早豆浆晚牛奶

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] parent = new int[1000];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = br.readLine()) != null) {
            if (s.equals("0")) break;
            String[] ss = s.split(" ");
            int n = Integer.parseInt(ss[0]);//n 城镇
            int m = Integer.parseInt(ss[1]);//m 道路
            for (int i = 1; i <= n; i++) {  //初始化父节点
                parent[i] = -1;
            }

            for (int i = 0; i < m; i++) {   //依次对每条路进行操作
                String[] str = br.readLine().split(" ");
                int x = Integer.parseInt(str[0]);
                int y = Integer.parseInt(str[1]);
                x = FindRoot(x);
                y = FindRoot(y);
                if (x != y) {  //两个点不属于一个集合，则连起来
                    parent[x] = y;
                }
            }

            int count = 0;    //找出此时有多少根节点，即多少个集合
            for (int i = 1; i <= n; i++) {
                if (parent[i] == -1) count++;
            }
            System.out.println(--count);

        }
    }

    public static int FindRoot(int t) {
        if (parent[t] == -1) return t;
        else {
            int r = FindRoot(parent[t]);
            parent[t] = r;    //  路径压缩
            return r;
        }
    }
}

发表于 2021-04-04 18:30:06 回复(0)

Java

LHC0512

Java 解法，使用并查集数据结构

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int townNum = scanner.nextInt();
            int pathNum = scanner.nextInt();
            UnionFind unionFind = new UnionFind(townNum+1);
            for (int i = 0; i < pathNum; i++) {
                int town1 = scanner.nextInt();
                int town2 = scanner.nextInt();
                unionFind.union(town1,town2);
            }
            TreeSet<Integer> set = new TreeSet<>();
            for (int i = 1; i <=townNum; i++) {
                set.add(unionFind.find(i));
            }
            System.out.println(set.size()-1);
        }
    }
    public static class UnionFind {
        private int[] id;

        public UnionFind(int N) {
            id = new int[N];
            for(int i = 0; i < N; i++) id[i] = i;
        }
        
        public int find(int p) {
            return id[p];
        }
        
        public void union(int p, int q){
            int pRoot = find(p);
            int qRoot = find(q);
            if(pRoot == qRoot) return;
            for(int i = 0; i < id.length; i++)
                if(id[i] == pRoot)  id[i] = qRoot;
        }
    }
}

发表于 2020-03-07 10:48:25 回复(0)