Cod sursa(job #574171)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 6 aprilie 2011 21:38:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

#define N 100005

vector<int> Gi[N],Gt[N],G[N];
vector<bool> viz;
stack<int> dr;

void DFI (int x){

	viz[x]=true;
	for(vector<int>::iterator i=Gi[x].begin();i<Gi[x].end();++i)
		if(viz[(*i)]==false)
			DFI(*i);
	dr.push(x);

	}

vector<int> drm;

void DFJ (int x, int v){

	drm[x]=v;
	for(vector<int>::iterator i=Gt[x].begin();i<Gt[x].end();++i)
		if(drm[(*i)]==-1)
			DFJ(*i,v);

	}

int main ()
{

	int n,m;
	ifstream in ("ctc.in");
	freopen ("ctc.out","w",stdout);
	in>>n>>m;
	for(;m;--m){
		int x,y;
		in>>x>>y;
		Gi[x].push_back(y);
		Gt[y].push_back(x);
		}
	viz.resize(n+1,false);
	for(int i=1;i<=n;++i)
		if(viz[i]==false)
			DFI(i);
	drm.resize(n+1,-1);
	int c=0;
	for(;!dr.empty();dr.pop())
		if(drm[dr.top()]==-1){
			DFJ(dr.top(),c);
			++c;
		}
    for(int i=1;i<=n;++i)
        G[drm[i]].push_back(i);
    printf("%d\n",c);
    for(int i=0;i<c;++i){
        for(vector<int>::iterator it=G[i].begin();it<G[i].end();++it)
            printf("%d ",(*it));
        printf("\n");
    }

	return 0;}