Cod sursa(job #371010)

Utilizator titusuTitus C titusu Data 3 decembrie 2009 00:05:09
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
using namespace std;
#define MAX 100010

struct nod{
	int info;
	nod * next;
};

nod * G[MAX], * GT[MAX];
int v[MAX], n, nrc, plus[MAX], minus[MAX];

void read(){
	freopen("ctc.in","r",stdin);
	int m , i , j;
	nod * p;
	scanf("%d%d", &n , &m);
	for(i = 1;i<=n;i++)
		G[i] = GT[i] = NULL;
	for( ; m ;--m){
		scanf("%d%d", &i ,&j);
		p= new nod ; p->info = j; p->next = G[i]; G[i] = p;
		p= new nod ; p->info = i; p->next = GT[j]; GT[j] = p;
	}
}

void write(){
	freopen("ctc.out","w", stdout);
	printf("%d\n", nrc);
	for(int i=1;i<=nrc;i++){
		for(int j=1;j<=n;j++)
			if(v[j]==i)
				printf("%d ", j);
		printf("\n");
	}
}


void parcurgere(int varf, nod * GRAF[], int v[]){
	v[varf]=1;
	for(nod *p = GRAF[varf]; p ; p = p -> next)
		if(!v[p->info])
			parcurgere(p->info, GRAF, v);
	
}

void plus_minus(){
	for(int i =1 ; i<=n;i++)
		if(v[i]==0){
			for(int j=1;j<=n;j++)
				plus[j]=minus[j]=0;
			parcurgere(i,G,plus);
			parcurgere(i,GT,minus);
			nrc++;
			for(int j=1;j<=n;j++)
				if(plus[j]+minus[j]==2)
					v[j] = nrc;
		}
}

int main(){
	read();
	plus_minus();
	write();
	return 0;
}