Cod sursa(job #3125969)

Utilizator Bianca7Popa Bianca Bianca7 Data 4 mai 2023 23:04:19
Problema Componente tare conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.17 kb
import java.util.Scanner;
import java.util.Stack;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;

public class Test {
    static class Task {
        public ArrayList<Integer> parent = new ArrayList<>();
        public ArrayList<Integer> low_link = new ArrayList<>();
        public ArrayList<Integer> found = new ArrayList<>();
        public Stack<Integer> stack = new Stack<>();
        public Integer time;

        // numarul maxim de noduri
        public static final int NMAX = (int) 1e5 + 5; // 10^5 + 5 = 100.005

        // n = numar de noduri, m = numar de muchii/arce
        int n, m;

        // adj[node] = lista de adiacenta a nodului node
        // exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
        @SuppressWarnings("unchecked")
        public ArrayList<Integer> adj[] = new ArrayList[NMAX + 1];

        public void solve() {
            readInput();
            writeOutput(getResult());
        }

        private void readInput() {
            try {
                Scanner sc = new Scanner(new BufferedReader(new FileReader("ctc.in")));
                n = sc.nextInt();
                m = sc.nextInt();

                for (int i = 1; i <= n; i++) {
                    adj[i] = new ArrayList<>();
                }
                for (int i = 1; i <= m; i++) {
                    int x, y;
                    x = sc.nextInt();
                    y = sc.nextInt();
                    adj[x].add(y); // arc (x, y)
                }
                sc.close();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        private void writeOutput(ArrayList<ArrayList<Integer>> all_sccs) {
            try {
                BufferedWriter bw = new BufferedWriter(new FileWriter("ctc.out"));
                StringBuilder sb = new StringBuilder();

                sb.append(all_sccs.size()).append("\n");

                for (ArrayList<Integer> scc : all_sccs) {
                    for (int node : scc) {
                        sb.append(node).append(" ");
                    }
                    sb.append("\n");
                }

                bw.write(sb.toString());
                bw.close();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        private void dfs(int node, ArrayList<ArrayList<Integer>> all_sccs) {
            ++time;
            found.set(node, time);
            low_link.set(node, found.get(node));
            stack.push(node);

            for (int neigh : adj[node]) {
                if (parent.get(neigh) != 0) {
                    if (stack.contains(neigh)) {
                        low_link.set(node, Math.min(low_link.get(node), found.get(neigh)));
                    }

                    continue;
                }

                parent.set(neigh, node);
                dfs(neigh, all_sccs);
                low_link.set(node, Math.min(low_link.get(node), low_link.get(neigh)));
            }

            if (low_link.get(node) == found.get(node)) {
                ArrayList<Integer> scc = new ArrayList<>();
                int top;

                do {
                    top = stack.peek();
                    scc.add(top);
                    stack.pop();
                } while (top != node);

                all_sccs.add(scc);
            }
        }

        private ArrayList<ArrayList<Integer>> getResult() {
            ArrayList<ArrayList<Integer>> all_sccs = new ArrayList<>();

            for (int i = 1; i <= n + 1; ++i) {
                parent.add(0);
                low_link.add(NMAX);
                found.add(NMAX);
            }

            time = 0;
            for (int i = 1; i <= n; ++i) {
                if (parent.get(i) == 0) {
                    parent.set(i, i);
                    dfs(i, all_sccs);
                }
            }

            return all_sccs;
        }
    }

    public static void main(String[] args) {
        new Task().solve();
    }
}