結果
問題 | No.679 不思議マーケット |
ユーザー |
|
提出日時 | 2018-04-27 23:35:04 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 288 ms / 2,000 ms |
コード長 | 2,569 bytes |
コンパイル時間 | 3,787 ms |
コンパイル使用メモリ | 79,908 KB |
実行使用メモリ | 47,736 KB |
最終ジャッジ日時 | 2024-06-27 22:24:09 |
合計ジャッジ時間 | 7,892 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder679 {private static Scanner sc;private static Printer pr;private static void solve() {int n = sc.nextInt();int m = sc.nextInt();List<List<Integer>> edges = new ArrayList<>(n);int[] cnt = new int[n];for (int i = 0; i < n; i++) {edges.add(new ArrayList<>());}for (int i = 0; i < m; i++) {int g = sc.nextInt() - 1;int r = sc.nextInt();for (int j = 0; j < r; j++) {int h = sc.nextInt() - 1;edges.get(h).add(g);cnt[g]++;}}int[] d = new int[n];int[] f = new int[n];int clock = 1;List<Integer> bt = new ArrayList<>();int[] used = new int[n]; // 0:White, 1:Gray, 2:Blackfor (int i = 0; i < n; i++) {if (used[i] != 0) {continue;}Deque<Integer> st = new ArrayDeque<>();st.push(i);while (!st.isEmpty()) {int e = st.peek();if (used[e] == 2) {st.pop();} else if (used[e] == 1) {// postorderf[e] = clock++;used[e] = 2;st.pop();} else {// preorderd[e] = clock++;used[e] = 1;for (int next : edges.get(e)) {if (used[next] == 2) {// 前進辺または横断辺continue;} else if (used[next] == 1) {// 後退辺bt.add(next);continue;}st.push(next);}}}}int[] used2 = new int[n];for (int i : bt) {if (used2[i] != 0) {continue;}Deque<Integer> st = new ArrayDeque<>();st.push(i);while (!st.isEmpty()) {int e = st.peek();if (used2[e] == 2) {st.pop();} else if (used2[e] == 1) {// postorderf[e] = clock++;used2[e] = 2;st.pop();} else {// preorderd[e] = clock++;used2[e] = 1;for (int next : edges.get(e)) {if (used2[next] == 2) {// 前進辺または横断辺continue;} else if (used2[next] == 1) {// 後退辺continue;}st.push(next);}}}}int ans = n;for (int ff : used2) {if (ff > 0) {ans--;}}pr.println(ans);}// ---------------------------------------------------public static void main(String[] args) {sc = new Scanner(INPUT == null ? System.in : new ByteArrayInputStream(INPUT.getBytes()));pr = new Printer(System.out);solve();// pr.close();pr.flush();// sc.close();}static String INPUT = null;private static class Printer extends PrintWriter {Printer(OutputStream out) {super(out);}}}