Cod sursa(job #3269261)

Utilizator lucky1992Ion Ion lucky1992 Data 18 ianuarie 2025 14:46:13
Problema Componente tare conexe Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 3.56 kb
import java.io.*;
import java.util.*;

public class Main {

  public static class MyScanner implements Closeable {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner(String file) throws FileNotFoundException {
      br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

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

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine(){
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

    @Override
    public void close() throws IOException {
      br.close();
    }
  }

  public static class DirectedGraph {

    private List<Integer>[] adjList;
    private int N;

    public DirectedGraph(int N) {
      this.N = N;
      adjList = (List<Integer>[]) new List[N+1];
    }

    public void addEdge(int u, int v) {
      if (adjList[u] == null) {
        adjList[u] = new ArrayList<>();
      }
      adjList[u].add(v);
    }

    public List<Integer> neighbors(int u) {
      if (adjList[u] == null) {
        return Collections.emptyList();
      } else {
        return adjList[u];
      }
    }

    public int size() {
      return N;
    }
  }

  public static int time = 0;
  public static Deque<Integer> stack = new ArrayDeque<>(512);
  public static boolean[] onStack;
  public static boolean[] visited;

  public static int[] discovery;
  public static int[] lowLink;

  public static List<List<Integer>> scc = new ArrayList<>();

  public static void dfsTarjanVisit(int u, DirectedGraph g) {
    visited[u] = true;
    time++;
    discovery[u] = time;
    lowLink[u] = time;

    stack.push(u);
    onStack[u] = true;

    for (int v : g.neighbors(u)) {
      if (!visited[v]) {
        dfsTarjanVisit(v, g);
        lowLink[u] = Math.min(lowLink[u], lowLink[v]);
      } else if (onStack[v]) {
        lowLink[u] = Math.min(lowLink[u], discovery[v]);
      }
    }

    if (lowLink[u] == discovery[u]) { // this root belongs to a scc
      List<Integer> newScc = new ArrayList<>();
      newScc.add(u);
      while (stack.peek() != u) {
        int fromStack = stack.pop();
        newScc.add(fromStack);
        onStack[fromStack] = false;
      }

      stack.pop();
      onStack[u] = false;
      scc.add(newScc);
    }

  }

  public static void dfsTarjan(DirectedGraph g) {

    for (int i = 1; i <= g.size(); i++) {
      if (!visited[i]) {
        dfsTarjanVisit(i, g);
      }
    }

  }

  public static void main(String[] args) throws IOException {
    try(MyScanner scanner = new MyScanner("ctc.in");
        PrintWriter fw = new PrintWriter(new FileOutputStream("ctc.out"))) {
      int N = scanner.nextInt();
      int M = scanner.nextInt();

      DirectedGraph g = new DirectedGraph(N);

      visited = new boolean[N+1];
      onStack = new boolean[N+1];
      discovery = new int[N+1];
      lowLink = new int[N+1];

      for (int i = 1; i <= M; i++) {
        g.addEdge(scanner.nextInt(), scanner.nextInt());
      }

      dfsTarjan(g);

      fw.println(scc.size());
      for (List<Integer> aScc : scc) {
        for (Integer comp : aScc) {
          fw.print(comp + " ");
        }
        fw.println();
      }
    }

  }
}