Cod sursa(job #2465399)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 30 septembrie 2019 08:42:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <stack>
#include <vector>
#include <fstream>

using namespace std;

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

const int MAXN = 1e5 + 5;
int viz[MAXN],nivel[MAXN],idk,iss[MAXN],n,L[MAXN],m,nrc;
vector < int > G[MAXN];
stack < int > s;
vector< int > ctc[MAXN];
void tarjan(int x) {
	
	iss[x] = true;
	viz[x] = true;
	s.push(x);
	nivel[x] = L[x] =++idk;
	for ( auto y : G[x]) {
		
		if ( !viz[y]) {
			tarjan(y);
			L[x] = min(L[y],L[x]);
		}
		else
			if ( iss[y] )
				L[x] = min(nivel[y],L[x]);
	}
	if (nivel[x] == L[x]) {
		++nrc;
		while ( !s.empty()) {
			
		ctc[nrc].push_back(s.top());
		iss[s.top()] = false;
		int y = s.top();
		s.pop();
		if ( y == x)
			break;
		}
		
	}
		
}
int main() {
	
	fin >> n >> m;
	for ( int x,y; m > 0; --m) {
		fin >> x >> y;
		G[x].push_back(y);
	}
	for ( int i = 1; i <= n; ++i)
		if ( !viz[i])
			tarjan(i);
	
	fout << nrc << "\n";
	for ( int i = 1;  i <= nrc; ++i,fout << "\n")
		for ( auto y : ctc[i])
			fout << y << " " ;
}