Cod sursa(job #383226)

Utilizator ilincaSorescu Ilinca ilinca Data 16 ianuarie 2010 01:41:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <stdio.h>
#include <string.h> 
#include <vector> 
#include <algorithm> 

#define nmax 100005
#define mmax 200005
#define pb push_back

using namespace std;

int n, m, t, nc, timp [nmax];
vector <pair <int, int> > vt (nmax);
vector <int> G [nmax];
vector <int> Gt [nmax];
vector <int> C [nmax];
bool viz [nmax];

void scan ()
{
	int i, a, b;
	scanf ("%d%d", &n, &m);
	for (i=1; i <= m; ++i) 
	{
		scanf ("%d%d", &a, &b);
		G [a].pb (b);
		Gt [b].pb (a);
	}
}

void init ()
{
	int i;
	for (i=1; i <= n; ++i) 
	{	
		vt.pb (make_pair (timp [i], i));
	//	fprintf(stderr, "%d %d\n", (vt.end ()-1)->first, (vt.end ()-1)->second); 
	}
}

void DFS1 (int nod)
{
	vector <int> :: iterator it;
	++t;
	viz [nod]=true;
	for (it=G [nod].begin (); it != G [nod].end () ; ++it) 
		if (viz [*it] == false) 
			DFS1 (*it);
	timp [nod] = ++t;
}

void DFS2 (int nod)
{
	vector <int> :: iterator it;
	C [nc].pb (nod);
	viz [nod]=true;
	for (it=Gt [nod].begin (); it != Gt [nod].end (); ++it) 
		if (viz [*it] == false) 
			DFS2 (*it);
}

void ctc ()
{
	int i;
	vector <pair <int, int> > :: iterator it;
	for (i=1; i <= n; ++i) 
		if (viz [i] == false) 
			DFS1 (i);
	memset (viz, 0, sizeof (viz));
	init ();
	sort (vt.begin (), vt.end ());
	for (it=vt.end (); it != vt.begin (); --it) 
	{
		//fprintf(stderr, "%d %d\n", vt [i].first, vt [i].second); 
		if (viz [it->second] == false) 
		{
			DFS2 (it->second);
			++nc;
		}
	}
	--nc;
}

void print ()
{
	int i;
	vector <int> :: iterator it;
	printf ("%d\n", nc);
	for (i=1; i <= nc; ++i) 
	{
		for (it=C [i].begin (); it != C [i].end (); ++it) 
			printf ("%d ", *it);
	       	printf ("\n");	
	}
}

int main ()
{
	freopen ("ctc.in", "r", stdin);
	freopen ("ctc.out", "w", stdout);
	scan ();
	ctc ();
	print ();
	return 0;
}