Cod sursa(job #371772)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 6 decembrie 2009 21:43:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
//Kosaraju
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define MAXN 100010
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector<int> G[2][MAXN];
stack<int> S;
int used[MAXN],WhatComp[MAXN],NComps;
vector< vector< int > > Comps;
int N,M;

void get_input(){
	fi>>N>>M;
	int x,y;
	for (int i=1;i<=M;++i){
		fi>>x>>y;
		G[0][x].push_back(y);
		G[1][y].push_back(x);
	}
	fi.close();
}

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

void DFMinus(int nod,vector<int>* G,int comp){
	WhatComp[nod]=comp;
	for (vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
		if (!WhatComp[*it])
			DFMinus(*it,G,comp);
}

void get_output(){
	fo<<NComps<<"\n";
	for (int i=0;i<NComps;++i){
		for (vector<int>::iterator it=Comps[i].begin();it!=Comps[i].end();++it)
			fo<<*it<<" ";
		fo<<"\n";
	}
}


int main(){
	get_input();
	
	memset(used,0,sizeof(used));
	memset(WhatComp,0,sizeof(WhatComp));

	for (int i=1;i<=N;++i) if (!used[i]) DFPlus(i,G[0]);

	NComps=0;

	while (!S.empty()){
		if (!WhatComp[S.top()]) { ++NComps; DFMinus(S.top(),G[1],NComps); }
		S.pop();
	}

	Comps.resize(NComps);

	for (int i=1;i<=N;++i) Comps[WhatComp[i]-1].push_back(i);

	get_output();

	return 0;
}