Cod sursa(job #3226729)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 22 aprilie 2024 17:26:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int const NMAX = 1e5;
vector <int> g[1 + NMAX];

int index;
int visit[1 + NMAX];
int minReach[1 + NMAX];
int onStack[1 + NMAX];

stack <int> st;

int ansSize = 0;
vector <int> ans[1 + NMAX];

void computeStrong(int node) {
  minReach[node] = node;
  index++;
  visit[node] = index;
  onStack[node] = true;
  st.push(node);
  for(int i = 0;i < g[node].size();i++) {
    int to = g[node][i];
    if(visit[to] == 0) {
      computeStrong(to);
      if(visit[minReach[to]] < visit[minReach[node]]) {
        minReach[node] = minReach[to];
      }
    }else if(onStack[to]){
      if(visit[minReach[to]] < visit[minReach[node]]) {
        minReach[node] = minReach[to];
      }
    }
  }
  if(minReach[node] == node) {
    ansSize++;
    while(st.top() != node) {
      ans[ansSize].push_back(st.top());
      onStack[st.top()] = false;
      st.pop();
    }
    ans[ansSize].push_back(node);
    onStack[node] = false;
    st.pop();
  }
}

int main() {

  int n, m;
  in >> n >> m;
  for(int i = 1;i <= m;i++) {
    int a, b;
    in >> a >> b;
    g[a].push_back(b);
  }
  for(int i = 1;i <= n;i++) {
    if(visit[i] == 0) {
      computeStrong(i);
    }
  }
  out << ansSize << '\n';
  for(int i = 1;i <= ansSize;i++) {
    for(int j = 0;j < ans[i].size();j++) {
      out << ans[i][j] << ' ';
    }
    out << '\n';
  }
  return 0;
}