Cod sursa(job #2184215)

Utilizator DimaTCDima Trubca DimaTC Data 23 martie 2018 20:48:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<bits/stdc++.h>
#define NMAX 100010
using namespace std;

stack<int>S;
int disc[NMAX],low[NMAX],k;
bool inS[NMAX];
vector<int>V[NMAX];
vector<int>CTC[NMAX];
int rs,n,m;

void tarjan(int x) {
	S.push(x); inS[x]=1;
	disc[x]=low[x]=++k;
	
	for (int i=0; i<V[x].size(); i++) {
		int y=V[x][i];
		if (!disc[y]) {
			tarjan(y);
			low[x]=min(low[x],low[y]);
		} else if (inS[V[x][i]])  {
			low[x]=min(low[x],disc[y]);
		}
	}
	
	if (disc[x]==low[x]) {
		int u; rs++;
		do {
			u=S.top(); inS[u]=0;
			CTC[rs].push_back(u); 
			S.pop();
		} while (u!=x);
	}
}

int main() {
	ifstream cin("ctc.in");
	ofstream cout("ctc.out");
	cin>>n>>m;
	
	for (int i=1; i<=m; i++) {
		int x,y; cin>>x>>y;
		V[x].push_back(y);
	}
	
	for (int i=1; i<=n; i++) 
		if (!disc[i]) tarjan(i);
		
	cout<<rs<<'\n';	
	for (int i=1; i<=rs; i++) {
		for (int j=0; j<CTC[i].size(); j++) {
			cout<<CTC[i][j]<<" ";
		} cout<<'\n';
	}	
	
	return 0;
}