Untitled
unknown
plain_text
10 months ago
2.6 kB
2
Indexable
Never
package Graph; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; class KhongMinh { public static int V; public static int[][] adj; public static int[] count; public static int[] cycleBoulders; public static int[] path; public static int pathIndex; public static int cycleCount; public static void findAllCycles(int v, boolean[] visited) { visited[v] = true; path[pathIndex] = v; pathIndex++; for (int i = 0; i < V; i++) { if (adj[v][i] == 1) { if (!visited[i]) { findAllCycles(i, visited); } else { if (pathIndex > 2 && path[0] == i) { // A cycle is found cycleCount++; for (int j = 0; j < pathIndex; j++) { int index = (cycleCount - 1) % pathIndex; cycleBoulders[cycleCount] += count[path[index]]; } } } } } pathIndex--; visited[v] = false; } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("Text")); // Read input from a file Scanner scanner = new Scanner(System.in); int tc = scanner.nextInt(); // Number of test cases for (int Case = 1; Case <= tc; Case++) { V = scanner.nextInt(); // Number of fortifications adj = new int[V][V]; count = new int[V]; cycleBoulders = new int[V + 1]; path = new int[V]; pathIndex = 0; cycleCount = 0; for (int i = 0; i < V; i++) { int index = scanner.nextInt(); count[index] = scanner.nextInt(); int gr = scanner.nextInt(); for (int j = 0; j < gr; j++) { int x = scanner.nextInt(); adj[i][x] = 1; } } boolean[] visited = new boolean[V]; for (int i = 0; i < V; i++) { if (!visited[i]) { findAllCycles(i, visited); } } System.out.println("Case #" + Case); if (cycleCount == 0) { System.out.println("No cycle found"); } else { for (int i = 1; i <= cycleCount; i++) { System.out.println(cycleBoulders[i]); } } } } }