Cod sursa(job #587214)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 4 mai 2011 09:12:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

#define Nmax 100001

int N, M, viz[Nmax], st[Nmax], nrcomp, cnt;
vector<int> G[Nmax], Gt[Nmax], sol[Nmax];
stack<int> S;

void DF(int nod) {
	if(viz[nod])
		return;
	viz[nod]=1;
	for(vector<int>:: iterator it=G[nod].begin(); it!=G[nod].end(); ++it)
		if(!viz[*it])
			DF(*it);
	S.push(nod);
}

void DF2(int nod) {
	if(viz[nod]==-1)
		return;
	viz[nod]=-1;
	st[++cnt]=nod;
	for(vector<int>:: iterator it=Gt[nod].begin(); it!=Gt[nod].end(); ++it)
		if(viz[*it]!=-1)
			DF2(*it);
}

void add() {
	int i;
	nrcomp++;
	for(i=1; i<=cnt; i++)
		sol[nrcomp].push_back(st[i]);
}

int main() {
	int i, j, nod;
	
	f>>N>>M;
	while(M--) {
		f>>i>>j;
		G[i].push_back(j);
		Gt[j].push_back(i);
	}
	for(i=1; i<=N; i++) 
		if(!viz[i])
			DF(i);
	while(!S.empty()) {
		nod=S.top();
		cnt=0;
		if(viz[nod]!=-1) {
			DF2(nod);
			add();
		}
		S.pop();
	}
	g<<nrcomp<<"\n";
	for(i=1; i<=nrcomp; i++) {
		for(vector<int>:: iterator it=sol[i].begin(); it!=sol[i].end(); ++it)
			g<<*it<<" ";
		g<<"\n";
	}
	
	f.close(); g.close();
	
	return 0;
}