Cod sursa(job #717004)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 19 martie 2012 15:18:36
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#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 DFS1 (int nod , int cost)
{
	pls[nod] = cost;
	
	for (unsigned int i = 0 ; i < lista[nod].size () ; ++i)
	{
		int nodcur = lista[nod][i];
		
		if (pls[nodcur] == cost)
			continue;
		
		pls[nodcur] = cost;
		DFS1 (nodcur , cost);
	}
}


void DFS2 (int nod , int cost)
{
	mns[nod] = cost;
	
	for (unsigned int i = 0 ; i < trans[nod].size () ; ++i)
	{
		int nodcur = trans[nod][i];
		
		if (mns[nodcur] == cost)
			continue;
		
		mns[nodcur] = cost;
		DFS2 (nodcur , cost);
	}
}


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);
	}
	
	int line = 0 , start;
	
	for (int i = 1 ; i <= N ; ++i)
		if (!marked[i])
		{
			start = i;
			
			++line;
			
			
			DFS1 (start , line);
			DFS2 (start , line);
			
			
			for (int i = 1 ; i <= N ; ++i)
				if (pls[i] == mns[i] && pls[i] != 0)
					marked[i] = pls[i];
		}
	
	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;
}