Untitled

mail@pastecode.io avatar
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]);
                }
            }
        }
    }
}