Cod sursa(job #396675)

Utilizator loginLogin Iustin Anca login Data 15 februarie 2010 18:37:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
# include <fstream>
# include <cstdio>
using namespace std;
struct nod {
	int info;
	nod *next;};
nod *g[100004], *gt[100003], *ctc[100003];
int n, m, final[100003], timp, v[100003], vt[100003], nrc;

void add (int i, int j)
{
	nod *q=new nod;
	q->info=j;
	q->next=g[i];
	g[i]=q;
}

void addt (int i, int j)
{
	nod *q=new nod;
	q->info=j;
	q->next=gt[i];
	gt[i]=q;
}

void read ()
{
	ifstream fin ("ctc.in");
	fin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int x, y;
		fin>>x>>y;
		add (x, y);
		addt (y, x);
	}
}

void afis ()
{
	freopen ("ctc.out", "w", stdout);
	printf("%d\n", nrc);
	for (int i=1;i<=nrc;i++)
	{
		nod *p=ctc[i];
		while (p)
		{
			printf("%d ", p->info);
			p=p->next;
		}	
		printf("\n");
	}
}

void dfs (int k)
{
	v[k]=1;
	for (nod *p=g[k];p;p=p->next)
		if (!v[p->info])
			dfs(p->info);
	final[++timp]=k;
}

void dfst (int k, int nrc)
{
	vt[k]=nrc;
	nod *q=new nod;
	q->info=k;
	q->next=ctc[nrc];
	ctc[nrc]=q;
	for (nod *p=gt[k];p;p=p->next)
		if (!vt[p->info])
			dfst(p->info, nrc);
}	

void kosaraju ()
{
	for (int i=1;i<=n;i++)
		if(v[i]==0)
			dfs(i);
	for (int i=timp;i;--i)
		if (vt[final[i]]==0)
		{
			++nrc;
			dfst(final[i], nrc);
		}
}

int main ()
{
	read ();
	kosaraju ();
	afis ();
	return 0;
}