[Java] UVa 10926 How Many Dependencies?

題目連結

題意:
有若干個 Task
彼此間有相依關係，分成直接與間接

如: A depends on B, and B depends on C
則可以說 A 有 2 個依賴，B 1個，C 0 個
(單向，A 對 B不能算給 B)
要找出依賴最高的 Task

每組測資有 N 個 Task (編號 1 ~ N)
題目會依序告知 N 個 Task 依賴的 Task 們

例如:
3
1 2
1 3

第 1 行表示有 3 個點
第 2 行為 Task 1
1 表示有 1 直接依賴到 Task 2
第 3 行為 Task 2
1 表示有 1 直接依賴到 Task 3
第 4 行為 Task 3

0 表示沒有依賴

最後輸出最高依賴的編號

如上例輸出 1 (Task 1 有 2 依賴最高)

解法:
當作圖論解
單向圖，以 DFS 或 BFS 走訪計算最大值
題目有說測資不會出現 cycle
也就是若 A 依賴 B，B 不可能依賴 A
所以單純找單向的直接與間接依賴即可

程式(Java):

	import java.util.*;
	public class Main {
	public static boolean[] visit = new boolean[101];
	public static int[] times = new int[101];
	public static boolean[][] map = new boolean[101][101];
	public static void DFS(int m, int s, int N) {
	for (int i = 1 ; i <= N; i++) {
	if (map[s][i] && !visit[i]) {
	visit[i] = true;
	times[m]++;
	DFS(m, i, N);
	}
	}
	}
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNext()) {
	int N = sc.nextInt();
	if (N == 0)
	break;
	Arrays.fill(visit, false);
	Arrays.fill(times, 0);
	for (int i = 0; i < 101; i++)
	Arrays.fill(map[i], false);
	for (int i = 1; i <= N; i++) {
	int T = sc.nextInt();
	while (T-- > 0) {
	int dir = sc.nextInt();
	map[i][dir] = true;
	}
	}
	int Max = 0;
	int index = 0;
	for (int i = 1; i <= N; i++) {
	Arrays.fill(visit, false);
	visit[i] = true;
	DFS(i, i, N);
	if (times[i] > Max) {
	Max = times[i];
	index = i;
	}
	}
	System.out.println(index);
	}
	}
	}

view raw UVa10926.java hosted with ❤ by GitHub