Cod sursa(job #716996)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 19 martie 2012 14:59:26
Problema Componente tare conexe Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define PB push_back
#define maxN 100005


int N , M , marked[maxN];
int pls[maxN] , mns[maxN];

vector <int> lista[maxN] , trans[maxN];
queue <int> Q;


void BFS (vector <int> graf[maxN] , int viz[maxN] , int start , int line)
{
	Q.push (start);
	viz[start] = line;
	
	while (!Q.empty ())
	{
		int nod = Q.front ();
		Q.pop ();
		
		for (unsigned int i = 0 ; i < graf[nod].size () ; ++i)
		{
			int nodcur = graf[nod][i];
			
			if (viz[nodcur] == line)
				continue;
			
			viz[nodcur] = line;
			Q.push (nodcur);
		}
	}
}


int main ()
{
	freopen ("ctc.in" , "r" , stdin);
	freopen ("ctc.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &M);
	
	int a , b;
	
	for (int i = 1 ; i <= M ; ++i)
	{
		scanf ("%d %d" , &a , &b);
		
		lista[a].PB (b);
		trans[b].PB (a);
	}
	
	bool done = false;
	int line = 0 , start;
	
	while (!done)
	{
		done = true;
		
		for (int i = 1 ; i <= N ; ++i)
			if (!marked[i])
			{
				start = i;
				
				done = false;
				break;
			}
		
		if (done)
			break;
		
		
		++line;
		
		
		BFS (lista , pls , start , line);
		BFS (trans , mns , start , line);
		
		
		for (int i = 1 ; i <= N ; ++i)
			if (pls[i] == mns[i] && pls[i] != 0)
				marked[i] = line;
		
	}
	
	printf ("%d\n" , line);
	
	for (int i = 1 ; i <= line ; ++i)
	{
		for (int j = 1 ; j <= N ; ++j)
			if (marked[j] == i)
				printf ("%d " , j);
		
		printf ("\n");
	}
	
	return 0;
}