Cod sursa(job #2500130)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 27 noiembrie 2019 11:50:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>

const int MAXN = 100000;

using namespace std;

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

int n, m, ans;

int id[1+MAXN+1], low[1+MAXN+1], lastId;

bool visited[1+MAXN+1];
bool inStack[1+MAXN+1];

stack<int> st;
vector<int> graph[1+MAXN+1], solution[1+MAXN+1];

void dfs(int node) {

  visited[node] = true;
  id[node] = low[node] = lastId++;

  st.push(node);
  inStack[node] = true;

  for(auto it:graph[node]) {
    if(!visited[it]) {
      dfs(it);

      low[node] = min(low[node], low[it]);
    }
    else if( inStack[it] ) {
      low[node] = min(low[node], low[it]);
    }
  }

  if(id[node] == low[node]) {
    ans++;

    bool found = false;

    while(!found) {
      found = (st.top() == node);

      solution[ans].push_back(st.top());
      inStack[st.top()] = false;

      st.pop();
    }
  }
}

int main() {

  fin>>n>>m;

  for(int i=1; i<=m; i++) {
    int x, y;

    fin>>x>>y;

    graph[x].push_back(y);
  }

  for(int i=1; i<=n; i++)
    if(!visited[i]) {
      dfs(i);
    }

  fout<<ans<<"\n";

  for(int i=1; i<=ans; i++) {
    for(auto it:solution[i]) {
      fout<<it<<" ";
    }

    fout<<"\n";
  }

  return 0;
}