Cod sursa(job #821491)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 22 noiembrie 2012 14:53:46
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<iostream>
#include<fstream>
using namespace std;

#define NMAX 100001

struct nod {
	int info;
	nod *urm;
};
typedef nod* PNOD;

PNOD v[NMAX],vt[NMAX];
int suc[NMAX],pred[NMAX],nc,n;

void adauga(PNOD &p, int y)
{
	PNOD aux;
	aux=new nod;
	aux->urm=p;
	aux->info=y;
	p=aux;
}

void citire()
{
	int m,x,y,i;
	ifstream f("ctc.in");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y;
		adauga(v[x],y);
		adauga(vt[y],x);
	}
	f.close();
}

void dfs(int nod)
{
	suc[nod]=nc;
	for(PNOD p=v[nod];p!=NULL;p=p->urm)
		if(suc[p->info]==0) 
			dfs(p->info);
}

void dfst(int nod)
{
	pred[nod]=nc;
	for(PNOD p=vt[nod];p!=NULL;p=p->urm)
		if(pred[p->info]==0) 
			dfst(p->info);
}

int main ()
{
	int i,j;
	citire();
	ofstream g("ctc.out");
	for(i=1;i<=n;i++)
		if(suc[i]==0) {
			nc++;
			suc[i]=nc;
			dfs(i);
			dfst(i);
			for(j=1;j<=n;j++)
				if(suc[j]!=pred[j])
					suc[j]=pred[j]=0;
		}
	g<<nc<<'\n';
	for(i=1;i<=nc;i++) {
		for(j=1;j<=n;j++)
			if(suc[j]==i)
				g<<j<<" ";
		g<<'\n';
	}
	g.close();
	return 0;
}