Cod sursa(job #2919462)

Utilizator euyoTukanul euyo Data 17 august 2022 18:11:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 100005;

vector<int> G[MAXN];
vector<vector<int>> comps;
vector<int> stk;
int dep[MAXN], _dep[MAXN], dd;
bool in[MAXN];

void dfs( int u ) {
  stk.push_back(u);
  in[u] = true;
  dep[u] = _dep[u] = dd++;
  for ( auto v : G[u] ) {
    if ( _dep[v] == -1 ) {
	  dfs(v);
	  dep[u] = min( dep[u], dep[v] );
	} else if ( in[v] ) {
	  dep[u] = min( dep[u], _dep[v] ); 
	}
  }
  if ( dep[u] == _dep[u] ) {
	vector<int> c;
    while ( stk.back() != u ) {
	  c.push_back(stk.back());
	  in[stk.back()] = false;
	  stk.pop_back();
	}
	c.push_back(u);
	in[u] = false;
	stk.pop_back();
	comps.push_back(c);
  }
}

int getNum() {
  int n = 0;
  char ch;
  while ( isspace( ch = fin.get() ) );
  do {
    n = n * 10 + ch - '0';
  } while ( isdigit( ch = fin.get() ) );
  return n;
}


int main() {
  int n, m, u, v;

  n = getNum(), m = getNum();
  while ( m-- ) {
	u = getNum(), v = getNum();
	G[u].push_back(v);
  }
  for ( int i = 1; i <= n; ++i ) {
	dep[i] = _dep[i] = -1;
  }
  for ( int i = 1; i <= n; ++i ) {
	if ( _dep[i] == -1 ) dfs(i);
  }
  fout << comps.size() << "\n";
  for ( auto c : comps ) {
	for ( auto x : c ) {
	  fout << x << " ";
	}
	fout << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}