Cod sursa(job #711045)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 11 martie 2012 11:23:48
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<fstream>
using namespace std;
#define lung 100001
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct nod{int val;
           nod *next;
};
nod *transp[lung],*v[lung],*rasp[lung],*q;
int i,n,m,nr,timp[lung],ordine[lung],final1;
bool viz1[lung],viz[lung];
inline void df(int x)
{nod *q=transp[x],*p;
    if (q)
	{   while (q)
	    {   if (!viz1[q->val])
		    {   viz1[q->val] = true;
				p = new nod;
				p -> val = q -> val;
				p -> next = rasp[nr];
				rasp[nr]= p;
				df(q->val);
			}
			q = q -> next;
		}
	}
}
inline void final(int x)
{nod *q=v[x];
	if (q)
	{	while (q)
		{   if (!viz[q->val])
		    {   viz[q->val] = true;
				final(q->val);
				++final1;
			}
		    q = q -> next;
		}
		timp[x] = final1;
    }
}
int main()
{int a,b,i;
    fin >> n >> m;
    for (i=1;i<=m;++i)
	{   fin >> a >> b;
	    q = new nod;
		q -> val = b;
		q -> next = v[a];
		v[a] = q;
		q = new nod;
		q -> val = a;
		q -> next = transp[b];
		transp[b] = q;
	}
	for (i=1;i<=n;++i)
		if (!viz[i])
		{	viz[i] = true;
			final(i);
		}
	for (i=1;i<=n;++i)
		ordine[n-timp[i]] = i;
	for (i=1;i<=n;++i)
		if (!viz1[ordine[i]])
		{   ++nr;
		    viz1[ordine[i]] = true;
			q = new nod;
			q -> val = ordine[i];
			q -> next = rasp[nr];
			rasp[nr] = q;
			df(ordine[i]);
		}
	fout << nr << '\n';
	for (i=1;i<=nr;++i)
	{   q = rasp[i];
	    while (q)
		{   fout << q -> val << " ";
			q = q -> next;
		}
		fout << '\n';
	}
	return 0;
}