Cod sursa(job #3296199)

Utilizator Radu_VasileRadu Vasile Radu_Vasile Data 12 mai 2025 10:02:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>
const int MAXN = 100'000;
const int MAXP2 = 65'536;
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);
}
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();
  fscanf(fin, "%d%d", &n, &m);
  for( int i = 0; i < m; i++ ) {
    int u, v;
    fscanf(fin, "%d%d", &u, &v);
    adj[u].push_back(v);
  }
  kosaraju.transpose_graph();
  kosaraju.get_scc();
  closeFiles();
  return 0;
}