リンク

https://www.acmicpc.net/problem/11724

質問する

方向図があるかどうかは、接続要素の数を計算するプログラムを作成します.

入力

第1行は、頂点の個数Nと、幹線の個数Mとを与える.(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N−1)/2)2行目から、幹線の両端点uおよびvがM行に与えられる.(1≦u,v≦N,u≠v)のような幹線は一度しか与えられない.

しゅつりょく

接続要素の数を最初の行に出力します.

に答える

import java.util.*;

public class boj_11724 {

    static ArrayList<Integer>[] arrayLists;
    static boolean visited[];

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

        arrayLists = new ArrayList[N+1];
        visited = new boolean[N+1];

        int vertex1, vertex2, answer = 0;

        for (int i = 1; i < N+1; i++) {
            arrayLists[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            vertex1 = scanner.nextInt();
            vertex2 = scanner.nextInt();

            arrayLists[vertex1].add(vertex2);
            arrayLists[vertex2].add(vertex1);
        }

        for (int i = 1; i < N+1; i++) {
            if (!visited[i]) {
                dfs(i);
                answer++;
            }
        }

        System.out.println(answer);

    }

    static void dfs(int v) {
        if(visited[v])
            return;

        visited[v] = true;
        for (int i : arrayLists[v]){
            if(!visited[i]) {
                dfs(i);
            }
        }
    }
}

説明:

問題では、まず「接続要素」自体が見慣れていない.幹線でつながっているノードグループを一つの接続要素と見なしているようで、探してみると、私の考えは正しいです.ノードと幹線の接続やナビゲーションにはまだ詳しくないので、参考リンク付きブログ記事を参考にして理解しました.

コメント

https://hees-dev.tistory.com/46