[백준] 1005 ACM Craft - JAVA

1. 문제 유형 : 위상정렬

2. 시간복잡도 : O(VE)

 

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

public class Main {

	public static class Node {
		int idx;
		Node link;

		public Node(int idx, Node link) {
			super();
			this.idx = idx;
			this.link = link;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		StringTokenizer st = null;
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(in.readLine());
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			int[] times = new int[N + 1];
			st = new StringTokenizer(in.readLine());
			for (int i = 1; i < N + 1; i++) {
				times[i] = Integer.parseInt(st.nextToken());
			}

			Node[] matrix = new Node[N+1];
			int[] degree = new int[N + 1];
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(in.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				matrix[a] = new Node(b, matrix[a]);
				degree[b]++;
			}
			
			int W = Integer.parseInt(in.readLine());
			int[] sum = new int[N+1];
			Queue<Integer> queue = new LinkedList<>();
			for (int i = 1; i < N + 1; i++) {
				if (degree[i] == 0) {
					queue.add(i);
					sum[i] = times[i];
				}
			}
			
			while (!queue.isEmpty()) {
				int idx = queue.poll();
				for(Node current=matrix[idx]; current!=null; current=current.link) {
					sum[current.idx] = Math.max(sum[current.idx], sum[idx]+times[current.idx]);
					degree[current.idx]--;
					if(degree[current.idx] == 0) {
						queue.add(current.idx);
					}
				}
			}
			System.out.println(sum[W]);
		}
	}

}