Cod sursa(job #2586854)

Utilizator leeviiTempfli Levente2 leevii Data 21 martie 2020 17:31:15
Problema Componente tare conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.2 kb
//tlim1969_L1_4.java
//Tempfli Levente, 514/1
//L1,F4
package tlim1969_L1_4;

import java.io.*;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

import static java.lang.Integer.min;

public class tlim1969_L1_4 {

    public static void main(String[] args) throws IOException {
        Graph graph = new Graph("ctc.in");

        ArrayList<LinkedList<Integer>> scc_components = graph.scc_tarjan();

        FileWriter fileWriter = new FileWriter("ctc.out");
        PrintWriter printWriter = new PrintWriter(fileWriter);

        printWriter.print(scc_components.size());
        for (LinkedList<Integer> ll : scc_components) {
            printWriter.print("\n");
            for (Integer e : ll) {
                printWriter.print(e);
                printWriter.print(" ");
            }
        }

        printWriter.close();
        fileWriter.close();
    }
}

class Graph {
    //Konstruktor-Beolvasas
    public Graph(String filename) throws FileNotFoundException {
        File file = new File(filename);
        Scanner scanner = new Scanner(file);

        int n, m;
        n = scanner.nextInt();
        m = scanner.nextInt();

        adj_list = new ArrayList<LinkedList<Integer>>();
        for (int i = 0; i <= n; i++) {
            adj_list.add(new LinkedList<Integer>());
        }
        seen = new ArrayList<Integer>(Collections.nCopies(n + 1, 0));
        low = new ArrayList<Integer>(Collections.nCopies(n + 1, 0));
        id = new ArrayList<Integer>(Collections.nCopies(n + 1, 0));
        stack = new Stack<Integer>();

        int f, g;
        for (int i = 0; i < m; i++) {
            f = scanner.nextInt();
            g = scanner.nextInt();
            adj_list.get(f).add(g);
        }


    }


    //Komponensek kiszamitasa
    public ArrayList<LinkedList<Integer>> scc_tarjan() {
        ArrayList<LinkedList<Integer>> components = new ArrayList<LinkedList<Integer>>();
        for (int i = 1; i < adj_list.size(); i++) {
            seen.set(i, 0);
        }
        stack.clear();

        for (int i = 1; i < adj_list.size(); i++) {
            if (seen.get(i) == 0) {
                DFSR_tarjan(components, i, 0);
            }
        }

        return components;
    }

    //Melysegi bejaras es tarjanozas
    private int DFSR_tarjan(ArrayList<LinkedList<Integer>> components, int i, int previd) {
        if (seen.get(i) == 2) return Integer.MAX_VALUE;
        if (seen.get(i) == 1) return low.get(i);
        id.set(i, previd + 1);
        stack.push(i);
        seen.set(i, 1);

        low.set(i, id.get(i));
        Iterator<Integer> it = adj_list.get(i).listIterator();
        while (it.hasNext()) {
            low.set(i,min(DFSR_tarjan(components, it.next(), id.get(i)), low.get(i)));
        }

        if (low.get(i) == id.get(i)) {
            components.add(new LinkedList<>());
            do {
                components.get(components.size() - 1).push(stack.peek());
                seen.set(stack.peek(), 2);
            } while (stack.pop() != i);
        }

        return low.get(i);
    }


    private ArrayList<LinkedList<Integer>> adj_list;
    private ArrayList<Integer> seen;
    private ArrayList<Integer> low;
    private Stack<Integer> stack;
    private ArrayList<Integer> id;
}