[白俊]1325号高効率ハッカー-Java,Java

難易度

銀色.

質問する

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

に答える

質問へのアクセス
この問題はDFSとBFSで解くことができるグラフィックナビゲーション問題で,私はBFSで解く.

最初に隣接行列を用いて問題を解いた結果,メモリ過剰が発生した.
Nが10000以下であるため,推定時間の複雑さにおいてO(N*N=10億程度)が出現し,これを減らすために隣接表(V+E)に変換した.

の基本的なBFS問題と同じように答えればよい.

問題を解く
result=ハッカー数を格納する配列
visit=アクセススケジュール
List=入力値を格納する隣接リスト

まず隣接リストを初期化し、値を入力します.

各ノードはBFSを実行し、各ノードのハッカー数を格納し、最大値を検索する.
入力した値をキューに入れ、アクセスを処理します.
キューが空でない場合
キューから値を減算します.
値に対応するリストを返します.
アクセスしない要素の場合は、アクセス処理を実行し、キューに要素を入れ、count++

最大値と同じノードを出力します.

コード#コード#

package 그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ1325 {
    static boolean[] visit;
    static int max = Integer.MIN_VALUE;
    static int n, m;
    static int count;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for(int i=0;i<=n;i++){
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(b).add(a);
        }
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            visit = new boolean[n + 1];
            count = 0;
            bfs(i);
            result[i] = count;
            max = Math.max(count, max);

        }
        for (int i = 1; i <= n; i++) {
            if (result[i] == max)
                sb.append(i+" ");
        }
        System.out.println(sb);

    }

    public static void bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        visit[x] = true;
        while (!q.isEmpty()) {
            int v = q.poll();
            for(int i : list.get(v)){
                if(!visit[i]){
                    q.add(i);
                    visit[i] = true;
                    count++;
                }
            }

        }
    }


}