Cod sursa(job #3296206)

Utilizator Radu_VasileRadu Vasile Radu_Vasile Data 12 mai 2025 10:08:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <bits/stdc++.h>
const int MAXN = 100'000;
const int MAXP2 = 65'536;
const int BUFSIZE = 131'072;
int n, m;
std::vector<int> adj[MAXN + 1];

FILE *fin, *fout;
void openFiles() {
  fin = fopen("ctc.in", "r");
  fout = fopen("ctc.out", "w");
}
void closeFiles() {
  fclose(fin);
  fclose(fout);
}
char rbuf[BUFSIZE];
int rpos = BUFSIZE - 1;
char readChar() {
  if(!(rpos = (rpos + 1) & (BUFSIZE - 1)))
    fread(rbuf, 1, BUFSIZE, fin);
  return rbuf[rpos];
}
int readInt() {
  char ch;
  while(!isdigit(ch = readChar()));
  int nr = 0;
  do{
    nr = nr * 10 + ch - '0';
  }while(isdigit(ch = readChar()));
  return nr;
}
struct Kosaraju {
  std::vector<int> tadj[MAXN + 1];
  bool viz[MAXN + 1];
  int postord[MAXN + 1];
  int nrp = 0;
  void transpose_graph() {
    for( int i = 1; i <= n; i++ ) {
      for( int node : adj[i] )
        tadj[node].push_back(i);
    }
  }
  void dfs1(int node) {
    viz[node] = 1;
    for(int nxt : adj[node]) {
      if(!viz[nxt])
        dfs1(nxt);
    }
    postord[nrp++] = node;
  }
  void reset_viz() {
    for( int i = 1; i <= n; i++ )
      viz[i] = 0;
  }
  void dfs2(int node, std::vector<int> &v) {
    viz[node] = 1;
    v.push_back(node);
    for( int nxt : tadj[node] ) {
      if(!viz[nxt])
        dfs2(nxt, v);
    }
  }
  void get_scc() {
    for( int i = 1; i <= n; i++ ) {
      if(!viz[i])
        dfs1(i);
    }
    reset_viz();
    std::vector<std::vector<int>> sol;
    for( int i = n - 1; i >= 0; i-- ) {
      if(!viz[postord[i]]) {
        std::vector<int> v;
        dfs2(postord[i], v);
        sol.push_back(v);
      }
    }
    fprintf(fout, "%d\n", sol.size());
    for( std::vector<int> &v : sol ) {
      for( int x : v ) {
        fprintf(fout, "%d ", x);
      }
      fprintf(fout, "\n");
    }
  }
}kosaraju;
int main(){
  openFiles();
  n = readInt();
  m = readInt();
  for( int i = 0; i < m; i++ ) {
    int u, v;
    u = readInt();
    v = readInt();
    adj[u].push_back(v);
  }
  kosaraju.transpose_graph();
  kosaraju.get_scc();
  closeFiles();
  return 0;
}