Cod sursa(job #1836454)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 28 decembrie 2016 13:23:47
Problema Componente tare conexe Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 3.07 kb
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
	    InputReader in = new InputReader(new FileInputStream("ctc.in"));
	    PrintWriter out = new PrintWriter(new FileOutputStream("ctc.out"));

	    int n = in.nextInt(), m = in.nextInt();
	    List<Integer>[] graph = new List[n];
	    for (int i = 0; i < n; i++) {
	        graph[i] = new ArrayList<>();
        }
	    for (int i = 0; i < m; i++) {
	        int x = in.nextInt() - 1;
	        int y = in.nextInt() - 1;
            graph[x].add(y);
        }
        List<List<Integer>> stronglyConnectedComponents = new Main().scc(graph);
	    out.println(stronglyConnectedComponents.size());
	    for (List<Integer> component: stronglyConnectedComponents) {
            for (Integer x: component) {
                out.print(x + 1);
                out.print(' ');
            }
            out.print('\n');
        }
        out.close();
    }

    List<Integer>[] graph;
    boolean[] visited;
    Stack<Integer> stack;
    int time;
    int[] lowlink;
    List<List<Integer>> components;


    public List<List<Integer>> scc(List<Integer>[] graph) {
        int n = graph.length;
        this.graph = graph;
        visited = new boolean[n];
        stack = new Stack<>();
        time = 0;
        lowlink = new int[n];
        components = new ArrayList<>();

        for (int u = 0; u < n; u++)
            if (!visited[u])
                dfs(u);

        return components;
    }

    void dfs(int u) {
        lowlink[u] = time++;
        visited[u] = true;
        stack.add(u);
        boolean isComponentRoot = true;

        for (int v : graph[u]) {
            if (!visited[v])
                dfs(v);
            if (lowlink[u] > lowlink[v]) {
                lowlink[u] = lowlink[v];
                isComponentRoot = false;
            }
        }

        if (isComponentRoot) {
            List<Integer> component = new ArrayList<>();
            while (true) {
                int x = stack.pop();
                component.add(x);
                lowlink[x] = Integer.MAX_VALUE;
                if (x == u)
                    break;
            }
            components.add(component);
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }

}