连通图

[编程题]连通图

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

给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

输入描述:

    每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。

输出描述:

    对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。

示例1

输入

输出

NO
YES

算法知识视频讲解

Java

nobodybutnobody

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

public class Main2 {
    //。bfs
    private static boolean isconnect(int N,long[][] tu){
        boolean ansflag = true;
        boolean[] isused = new boolean[N];
        List<Integer> jxlist = new ArrayList<>();
        isused[0] = true;
        jxlist.add(0);

        while (!jxlist.isEmpty()){
            int jx = jxlist.get(0);
            jxlist.remove(0);
            for (int i =0;i<N;i++){
                if (!isused[i] && tu[jx][i]!=0){
                    isused[i] = true;
                    jxlist.add(i);
                }
            }
        }

        for (int i=0;i<N;i++){
            if (!isused[i])
                ansflag = false;
        }

        return ansflag;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long M = sc.nextInt();
        long[][] tu = new long[N][N];
        

        for (int i=0;i<M;i++){
            int u = sc.nextInt(),v = sc.nextInt();

            tu[u-1][v-1] = 1;
            tu[v-1][u-1] = 1;
            

        }

        if (isconnect(N,tu)){
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
        sc.close();

    }
}

发表于 2020-04-29 09:03:56 回复(0)

Java

LHC0512

Java 解法，使用并查集

package nowcoder02.demo49;

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    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;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int vertex = scanner.nextInt();
            int edge = scanner.nextInt();
            UnionFind union = new UnionFind(vertex + 1);
            for (int i = 0; i < edge; i++) 
                union.union(scanner.nextInt(),scanner.nextInt());
            HashSet<Integer> set = new HashSet<>();
            for (int i = 0; i < vertex; i++) 
                set.add(union.find(i+1));
            System.out.println(set.size()==1?"YES":"NO");
        }
    }
}

发表于 2020-03-14 11:12:23 回复(0)