Cod sursa(job #717010)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 19 martie 2012 15:23:00
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

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 ()
{
	ifstream f ("ctc.in");
	ofstream g ("ctc.out");
	
	f >> N >> M;
	
	int a , b;
	
	for (int i = 1 ; i <= M ; ++i)
	{
		f >> a >> b;
		
		lista[a].PB (b);
		trans[b].PB (a);
	}
	
	int line = 0 , start;
	
	for (int i = 1 ; i <= N ; ++i)
		if (!marked[i])
		{
			start = i;
			
			++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] = pls[i];
		}
	
	g << line << "\n";
	
	for (int i = 1 ; i <= line ; ++i)
	{
		for (int j = 1 ; j <= N ; ++j)
			if (marked[j] == i)
				g << j << " ";
		
		g << "\n";
	}
	
	return 0;
}