Cod sursa(job #1836449)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 28 decembrie 2016 13:18:15
Problema Componente tare conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.23 kb
import java.util.*;
import java.io.*;
import java.lang.*;
import java.util.stream.Stream;

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 = 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();
    }

    public static List<List<Integer>> scc(List<Integer>[] graph) {
        int n = graph.length;
        int[] stack = new int[n];
        int st = 0;
        int[] stack_cur = new int[n];
        int[] stack_pos = new int[n];
        int[] stack_prev = new int[n];
        int[] index = new int[n];
        Arrays.fill(index, -1);
        int[] lowlink = new int[n];
        int time = 0;
        List<List<Integer>> components = new ArrayList<>();

        for (int u = 0; u < n; u++) {
            if (index[u] == -1) {
                int top = 0;
                stack_cur[top] = u;
                stack_pos[top] = 0;
                stack_prev[top] = -1;
                while (top >= 0) {
                    int cur = stack_cur[top];
                    int pos = stack_pos[top];
                    if (index[cur] == -1) {
                        index[cur] = time;
                        lowlink[cur] = time;
                        ++time;
                        stack[st++] = cur;
                    }
                    if (pos < graph[cur].size()) {
                        int v = graph[cur].get(pos);
                        ++stack_pos[top];
                        if (index[v] == -1) {
                            ++top;
                            stack_cur[top] = v;
                            stack_pos[top] = 0;
                            stack_prev[top] = cur;
                        } else {
                            lowlink[cur] = Math.min(lowlink[cur], lowlink[v]);
                        }
                    } else {
                        int prev = stack_prev[top];
                        if (prev != -1) {
                            lowlink[prev] = Math.min(lowlink[prev], lowlink[cur]);
                        }
                        if (lowlink[cur] == index[cur]) {
                            List<Integer> component = new ArrayList<>();
                            while (true) {
                                int v = stack[--st];
                                lowlink[v] = Integer.MAX_VALUE;
                                component.add(v);
                                if (v == cur)
                                    break;
                            }
                            components.add(component);
                        }
                        --top;
                    }
                }
            }
        }

        return components;
    }

    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());
        }
    }

}