Cod sursa(job #3353870)

Utilizator ultra980Alex Stan ultra980 Data 12 mai 2026 11:46:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>

#include <vector>
#include <stack>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int NODES = 1e5 + 1;

int n, m, k;

//int adj[NODES][NODES];
// int rev[NODES][NODES];
vector<int> adj[NODES], rev[NODES];
vector<bool> viz(NODES,false);
stack<int> ord_st;
vector<vector<int>> components;

void init_dfs(int c) {
  viz[c] = true;
  for (const int &nxt : adj[c]) {
    if (!viz[nxt]) {
      init_dfs(nxt);
    }
  }
  ord_st.push(c);
}

void rev_dfs(int c, vector<int> &comp) {
  // printf("    rev_dfs(%d)\n", c);
  viz[c] = true;
  comp.push_back(c);

  for (const int &nxt : rev[c]) {
    // printf("      vreau sa merg in %d; viz: %d\n", nxt, (int)viz[nxt]);
    if (!viz[nxt]) {
      rev_dfs(nxt, comp);
    }
  }
}

void kosaraju() {
  int i;
  

  for (i = 1; i <= n; ++i) {
    if (!viz[i]) {
      init_dfs(i);
    }
  }
  // // printf("gata dfs 1\n");

  fill(viz.begin(), viz.end(), false);

  while (!ord_st.empty()) {
    // printf("ord_st are %lu elem\n", ord_st.size());
    int top = ord_st.top();
    // printf("  viz[%d] = %d\n", top, (int)viz[top]);
    ord_st.pop();
    if (!viz[top]) {
      vector<int> comp;
      // printf("dau rev_dfs(%d, comp, %lu)\n", top, components.size());
      rev_dfs(top, comp);
      components.push_back(comp);
    }
  }
}

int main() {
  fin >> n >> m;
  // printf("n %d m %d\n", n, m);
  int i, x, y;

  for (i = 0; i < m; ++i) {
    fin >> x >> y;
    // printf("%d -> %d\n", x, y);
    adj[x].push_back(y);
    rev[y].push_back(x);
  }

  kosaraju();

  fout << components.size() << '\n';
  for (auto comp : components) {
    for (int v : comp) {
      fout << v << ' ';
    }
    fout << '\n';
  }
}