ABC075 C （DFS）

問題

• DFS の基礎の基礎
• これができなきゃ話にならない
• 今回鍵となるのは変数をグローバル変数にすること
• staticメソッドとしてDFSを定義するので、DFS関数内で使用したい文字はグローバル変数として定義しておかなくてはならない.
• 入力のあたいの数が50と小さいため全探索をして十分に間に合った。

配列の取り扱い

int a[] ;

これで配列の参照の変数名の定義が終わる.実際には配列は生成されていない.

a = new int[要素数];

これを行うことでaという配列が実際に生成される.

解答

import java.util.Scanner;

public class Main {
    static int a[];
    static int b[];
    static boolean move[][];
    static boolean vis[];
    static int m;
    static int n;

• まずはじめにグローバル変数の定義をしてしまう

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[m];
        b = new int[m];
        move = new boolean[n + 1][n + 1];
        vis = new boolean[n + 1];
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                move[i][j] = false;
            }
        }
        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
            move[a[i]][b[i]] = true;
            move[b[i]][a[i]] = true;
        }
        // 一つずつ線を消していく
        int ans = 0;
        boolean conected = true;
        for (int i = 0; i < m; i++) {
            move[a[i]][b[i]] = false;
            move[b[i]][a[i]] = false;
            // 初期化する
            for (int j = 0; j < n + 1; j++) {
                vis[j] = false;
            }
            conected = true;
            dfs(1);
            vis[0] = true;
            for (int j = 0; j < n + 1; j++) {
                if (!vis[j]) {
                    conected = false;
                }
            }
            if (!conected) {
                ans++;
            }
            move[a[i]][b[i]] = true;
            move[b[i]][a[i]] = true;

        }
        System.out.println(ans);

    }

• ここからがDFSメソッドの中身 推移してを繰り返している for文を回していることで同じ場所から二つの場所へいく対策もできている.

    static void dfs(int x) {
        if (vis[x])
            return;
        vis[x] = true;
        for (int i = 1; i < n + 1; i++) {
            if (move[x][i]) {
                dfs(i);
            }
        }
    }
}