Indeedなう A日程 E: Page Rank

問題

E: Page Rank - Indeedなう（オープンコンテスト） | AtCoder

解法

最初に全社員のPage Rank を1.0としておき、定義にしたがって1000回ほど計算すると収束する。

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		ArrayList<ArrayList<Integer>> nLists = new ArrayList<>();
		ArrayList<ArrayList<Integer>> mLists = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			nLists.add(new ArrayList<Integer>());
			mLists.add(new ArrayList<Integer>());
		}
		// lists.get(i):= iを優秀だと思っている社員のリスト

		for (int i = 0; i < M; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			nLists.get(a).add(b);
			mLists.get(b).add(a);
		}

		double[] pageRank = new double[N];
		Arrays.fill(pageRank, 1.0);

		for (int q = 0; q < 1000; q++) {
			for (int i = 0; i < N; i++) {
				double sum = 0;
				for (int a = 0; a < mLists.get(i).size(); a++) {
					int j = mLists.get(i).get(a);
					sum += pageRank[j] / nLists.get(j).size();
				}
				pageRank[i] = 0.1 + 0.9 * sum;
			}
		}

		for (int i = 0; i < pageRank.length; i++) {
			System.out.println(pageRank[i]);
		}

	}
}