Cod sursa(job #371014)

Utilizator titusuTitus C titusu Data 3 decembrie 2009 00:18:11
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <cstring>
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],coada[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 dfs(int varf, nod * GRAF[], int v[]){
	v[varf]=1;
	for(nod *p = GRAF[varf]; p ; p = p -> next)
		if(!v[p->info])
			dfs(p->info, GRAF, v);
	
}

void bfs(int start, nod * GRAF[], int v[]){
	int st=1, dr=1, k,kk;
	coada[dr]=start; v[start] = 1;
	while(st<=dr){
		k = coada[st++];
		for(nod *p =  GRAF[k]; p ; p = p -> next)
			if(!v[kk = p->info]){
				v[kk] =1;
				coada[++dr] = kk;
			}
	}
}

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

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