Cod sursa(job #2650372)

Utilizator BereaBerendea Andrei Berea Data 18 septembrie 2020 16:00:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
//#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
int x,y;
int nrcomp;
stack<int>s;
const int MAXN=100001;
vector < int > g[MAXN];
vector<int>ctc[MAXN];
int viz[MAXN];
int iss[MAXN]; // is it in stack?    1 daca nodul se afla in stiva, 0 daca nu
int nivel[MAXN],idk;
int L[MAXN];// label

ifstream cin("ctc.in");
ofstream cout("ctc.out");
void tarjan(int x) {
	viz[x] = 1;
	iss[x] = 1;
	s.push(x);
	nivel[x] = ++idk;
	L[x] = nivel[x];
	for ( auto y : g[x]) {
	if(!viz[y]) {
	tarjan(y);
	L[x] = min(L[x],L[y]);
}
	else
	if(iss[y]) {
		L[x] = min(nivel[y],L[x]); // am descoperit o muchie de
}


}
	if(nivel[x] == L[x]) { // am gasit tatal componentei, si-a terminat dfs-ul, atunci toata componeta este gata(e descoperită)
	++nrcomp;
while(!s.empty()) {
	int y = s.top();
	s.pop();
	iss[y]=false;
	ctc[nrcomp].push_back(y);
	if(y == x)
		break;
}
}
}

int n,m;
int main() {
		cin >> n >>m;
	for ( int i = 1; i <= m; ++i) {
	cin >> x >> y;
	g[x].push_back(y);
}
	for ( int i = 1; i <= n; ++i)
		if(!viz[i])
			tarjan(i);

    cout << nrcomp <<"\n";
for (int i = 1; i <=nrcomp; ++i) {
	for ( auto y : ctc[i])
		cout << y <<" ";
cout << "\n";
}

}