AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 商店
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 3587. 连通图 0.02 AC币

作者: 作者的头像   Changersh ,  2022-07-07 14:07:31 ,  所有人可见 ,  阅读 7


0


/**
 * @author Changersh
 * method 并查集
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int[] pre = new int[1002]; // 标记数组,有没有走过
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();

            for (int i = 1; i <= n; i++) pre[i] = i;

            for (int i = 0; i < m; i++) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();

                pre[find(a)] = find(b);
            }

            int res = 0;
            for (int i = 1; i <= n; i++) {
                if (find(i) == i) res++;
            }
            if (res > 1) System.out.println("NO");
            else System.out.println("YES");
        }
    }

    public static int find(int x) {
        if (pre[x] != x) {
            pre[x] = find(pre[x]);
        }
        return pre[x];
    }
}

0 评论

你确定删除吗?
1024
x

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息