Cod sursa(job #266806)

Utilizator andreisfrentSfrent Andrei andreisfrent Data 26 februarie 2009 09:36:26
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <stdio.h>
#include <queue>
using namespace std;

#define N 100001
#define M 200001

struct muchie { int x, y; };

int *a[N], *at[N];
int vec_a[N], vec_at[N];
int n, m;
muchie vm[M];
int s[N], p[N];
int ncc = 0;

queue<int> coada;

void citeste_graf()
{
	scanf("%d%d", &n, &m);
	int i, nodX, nodY;
	
	for(i=0;i<m;++i)
	{
		scanf("%d%d", &nodX, &nodY);
		vm[i].x = nodX;
		vm[i].y = nodY;
		vec_a[nodX]++;
		vec_at[nodY]++;
	}
	
	for(i=1;i<=n;++i)
	{
		a[i] = new int[vec_a[i]+1];
		at[i] = new int[vec_at[i]+1];
		a[i][0] = 0;
		at[i][0] = 0;
	}
	
	for(i=0;i<m;++i)
	{
		nodX = vm[i].x;
		nodY = vm[i].y;
		
		a[nodX][++a[nodX][0]] = nodY;
		at[nodY][++at[nodY][0]] = nodX;
	}
}

void breadth_first_1(int start)
{
	int e, i;
	coada.push(start);
	s[start] = ncc;
	while(!coada.empty())
	{
		e = coada.front();
		coada.pop();
		for(i=1;i<=a[e][0];++i)
		{
			if(!s[a[e][i]])
			{
				s[a[e][i]] = ncc;
				coada.push(a[e][i]);
			}
		}
	}
}

void breadth_first_2(int start)
{
	int e, i;
	coada.push(start);
	p[start] = ncc;
	while(!coada.empty())
	{
		e = coada.front();
		coada.pop();
		for(i=1;i<=at[e][0];++i)
		{
			if(!p[at[e][i]])
			{
				p[at[e][i]] = ncc;
				coada.push(at[e][i]);
			}
		}
	}
}

int main()
{
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	
	citeste_graf();
	
	int i, j;
	
	for(i=1;i<=n;++i)
	{
		if(s[i] == 0)
		{
			++ncc;
			breadth_first_1(i);
			breadth_first_2(i);
			for(j=1;j<=n;++j) if(s[j]!=p[j]) s[j]=p[j]=0;
		}
	}
	
	printf("%d\n", ncc);
	
	for(i=1;i<=ncc;++i)
	{
		for(j=1;j<=n;++j) if(s[j] == i) printf("%d ", j);
		printf("\n");
	}
	
	fclose(stdin);

	return 0;
}