Untitled
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