Cod sursa(job #716947)

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

using namespace std;

#define PB push_back
#define maxN 100005


int N , M , sol[maxN][100];
bool pls[maxN] , mns[maxN] , marked[maxN];

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


void BFS (vector <int> graf[maxN] , bool viz[maxN] , int start)
{
	Q.push (start);
	viz[start] = true;
	
	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])
				continue;
			
			viz[nodcur] = true;
			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;
				
				marked[i] = true;
				break;
			}
		
		if (done)
			break;
		
		BFS (lista , pls , start);
		BFS (trans , mns , start);
		
		++line;
		
		for (int i = 1 ; i <= N ; ++i)
			if (pls[i] && mns[i])
			{
				++sol[line][0];
				
				
				int aux = sol[line][0];
				sol[line][aux] = i;
				
				marked[i] = true;
			}
		
		memset (pls , 0 , sizeof (pls));
		memset (mns , 0 , sizeof (mns));
	}
	
	printf ("%d\n" , line);
	
	for (int i = 1 ; i <= line ; ++i)
	{
		for (int j = 1 ; j <= sol[i][0] ; ++j)
			printf ("%d " , sol[i][j]);
		
		printf ("\n");
	}
	
	return 0;
}