Cod sursa(job #2919437)

Utilizator euyoTukanul euyo Data 17 august 2022 17:13:06
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 100005;

vector<int> G[MAXN], Gt[MAXN];
vector<vector<int>> comps;
bool viz[MAXN];

vector<int> nodes, comp;

void dfs_order( int u ) {
  viz[u] = true;
  for ( auto v : G[u] ) {
	if ( !viz[v] ) {
	  dfs_order(v);
	}
  }
  nodes.push_back(u);  
}
void dfs_comp( int u ) {
  viz[u] = true;
  comp.push_back(u);
  for ( auto v : Gt[u] ) {
	if ( !viz[v] ) {
	  dfs_comp(v);
	}
  }
}

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

  fin >> n >> m;
  while ( m-- ) {
	fin >> u >> v;
	G[u].push_back(v);
	Gt[v].push_back(u);
  }
  dfs_order(1);
  for ( int i = 1; i <= n; ++i ) viz[i] = false;
  while ( nodes.size() ) {
	int u = nodes.back();
	nodes.pop_back();
	if ( !viz[u] ) {
      comp.clear();
	  dfs_comp(u);
	  comps.push_back(comp);
	}
  }
  fout << comps.size() << "\n"; 
  for ( auto c : comps ) {
	for ( auto x : c ) {
	  fout << x << " ";
	}
	fout << "\n";
  }
  
  fin.close();
  fout.close();
  return 0;
}