Java实现 蓝桥杯VIP 算法训练 连通分块（并查集）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java实现 蓝桥杯VIP 算法训练 连通分块（并查集），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1062字，纯文字阅读大概需要2分钟。

内容图文

试题 算法训练 连通分块

资源限制
时间限制：200ms 内存限制：8.0MB

问题描述
　　连通分块
输入格式
　　输入的第一行包含两个整数n, m
　　n代表图中的点的个数，m代表边的个数
　　接下来m行，每行2个正整数，表示图中连通的两点。
输出格式
　　输出1行，与1连通的点的集合，并按升序排列输出。
样例输入
6 3
1 2
2 3
3 4
样例输出
1 2 3 4
数据规模和约定
　　n<=10000,m<=100000

package 蓝桥杯官网;

import java.util.Scanner;

public class 连通分块 {

    //https://blog.csdn.net/a1439775520/article/details/90746562  欢迎进入讨论群
    public static int[] f;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        f = new int[n + 1];
        int x, y;
        for (int i = 1; i <= n; i++) {
            f[i] = i;
        }
        for (int i = 0; i < m; i++) {
            x = sc.nextInt();
            y = sc.nextInt();
            setinfo(x, y);
        }
        for (int i = 1; i <= n; i++) {
            if (f[i] == 1) System.out.print(i + " ");
        }

    }

    public static void setinfo(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa > fb) {
            f[fa] = fb;
        } else {
            f[fb] = fa;
        }
    }

    public static int find(int num) {
        if (num != f[num]) {
            int temp = find(f[num]);
            f[num] = temp;
        }
        return f[num];
    }
}

内容总结

以上是互联网集市为您收集整理的Java实现 蓝桥杯VIP 算法训练 连通分块（并查集）全部内容，希望文章能够帮你解决Java实现 蓝桥杯VIP 算法训练 连通分块（并查集）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---