Untitled

 avatar
unknown
plain_text
a year ago
2.6 kB
6
Indexable
package samsung_srv_training.dfs;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

public class DiamondInheritance {
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("src/samsung_srv_training/dfs/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

//        long begin = System.currentTimeMillis();
        for (int tc = 0; tc < T; tc++) {
            int v = sc.nextInt();
            int[][] mat = new int[v+1][v+1];
            int[] dem = new int[v+1];
            for (int i = 1; i <= v; ++i) {
                int adj = sc.nextInt();
                dem[i] = adj;
                if (adj > 0) {
                    for (int j = 1; j <= adj; ++j) {
                        int y = sc.nextInt();
                        mat[i][y] = 1;
                    }
                }
            }

            Stack stack = new Stack();
            boolean[] visited;
            boolean flag = true;
            for (int i = 1; i <= v; ++i) {
                if (dem[i] >= 2) {
                    stack.removeAllElements();
                    visited = new boolean[v+1];

                    // exe dfs
                    stack.push(i);
                    while (!stack.empty()){
                        int  temp =(int) stack.pop();
                        visited[temp] = true;
                        for (int j = 1; j <= v; ++j) {
                            if (j != temp) {
                                if (mat[temp][j] == 1) {
                                    if (!visited[j]) {
                                        stack.push(j);
                                        visited[j] = true;
                                    } else {
                                        flag = false;
                                        break;
                                    }
                                }
                            } else {
                                continue;
                            }
                        }
                        if (!flag) break;
                    }
                    if (!flag) break;
                }
            }
            if (!flag) {
                System.out.println("Case #" + (tc+1) + ": Yes");
            } else {
                System.out.println("Case #" + (tc+1) + ": No");
            }
        }
//        System.out.println(System.currentTimeMillis()- begin);
    }
}
Editor is loading...
Leave a Comment