13023 ABCDE

タイムアウトメモリコミット正解率2秒512 MB 19011587339329.41%

質問する

BOJアルゴリズムキャンプにはN人が参加している.人々は0番からN-1番で、友达がいる.
今日は以下のような友人関係のある人A,B,C,D,Eが存在するかどうかを検討してみましょう.

AとBは友達です.

BとCは友達です.

CとDは友達です.

DとEは友達です.

上記の友人関係があるかどうかを判断するプログラムを作成してください.

入力

第1行は、人の数N(5≦N≦2000)と友人関係の数M(1≦M≦2000)を与える.
2行目から、M行には整数aとbがあり、aとbが友達であることを示す.(0≦a,b≦N−1,a≠b)2回以上の友人関係はない.

しゅつりょく

問題条件に合致するA,B,C,D,Eがあれば、1がなくて出力0となる.

入力例1

5 4
0 1
1 2
2 3
3 4

サンプル出力1

1

入力例2

5 5
0 1
1 2
2 3
3 0
1 4

サンプル出力2

1

入力例3

6 5
0 1
0 2
0 3
0 4
0 5

サンプル出力3

0

入力例4

8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7

サンプル出力4

1

コード#コード#

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class P_13023 {

    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static boolean status;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] friend_info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        graph = new ArrayList[friend_info[0]];
        for (int i = 0; i < friend_info[0]; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < friend_info[1]; i++) {
            int[] friend = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int from = friend[0];
            int to = friend[1];

            graph[from].add(to);
            graph[to].add(from);
        }

        for (int i = 0; i < friend_info[0]; i++) {
            if (!status) {
                visited = new boolean[friend_info[0]];
                dfs(i, 1);
            }
        }

        if (status) bw.write(Integer.toString(1));
        else bw.write(Integer.toString(0));
        bw.flush();
    }

    public static void dfs(int idx, int depth) {
        if (depth == 5) {
            status = true;
            return ;
        }
        else {
            visited[idx] = true;
            for (int num : graph[idx]) {
                if (!visited[num]) dfs(num, depth + 1);
            }
            visited[idx] = false;
        }
    }
}

コードの説明

問題はA-B-C-D-Eが満足しているかどうかです.
つまり、少なくとも5人は一緒にいる友達でなければなりません.
そこでDFSを使用しました.
グラフはarraylist資料型を用い,配列を宣言し,各インデックスにarraylist資料型がある.
友达になるのは无方向干线図で、もし2つの頂点をあげるならば、2つのインデックスにすべてプラスしました.
dfsは、すべての頂点を起点とすることができるので、各頂点はdfsを呼び出す.
dfsメソッドには、参照するインデックスidxと、ループの深さを表す深さ係数があります.
この深さが5の場合、5人の友達がいることを示し、statusをtrueに変更し、dfsを終了します.
[アクセス](Access)頂点にアクセスしたかどうかを確認します.
trueはアクセス済み、falseは未アクセスを表します.
dfsは、idxへのアクセスをtrueとして開始する.
その後、idx接続のすべての頂点へのアクセスがfalseの場合、dfs関数が再び呼び出されます.
この問題は、すべてのグラフを巡視するときに5人の友達がいるかどうかを確認するため、巡視が終わるとアクセスがfalseに変更されます.