Cod sursa(job #394949)

Utilizator SzabiVajda Szabolcs Szabi Data 11 februarie 2010 20:21:39
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <string.h>

struct adat{
adat* kov;
int x;
bool lattam;

adat(){ kov=0;
		lattam=false;}};

typedef adat* tipus;

tipus a[100001];
int n,m,comp=0;

void beszur(int hova,int mit){
tipus temp=a[hova];

if(temp==0){
a[hova]=new adat;
a[hova]->x=mit;
}else{
	while(temp->kov!=0){temp=temp->kov;}
	temp->kov=new adat;
	temp->kov->x=mit;
}

}

void bejar(int i){
tipus temp=a[i];
while(temp!=0){
bejar(temp->x);
temp=temp->kov;

}

}

int main(){
int i,temp1,temp2;
adat b;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);

scanf("%d %d",&n,&m);
memset(a,0,(n+2)*12);

for(i=1;i<=m;i++){
scanf("%d %d",&temp1,&temp2);
beszur(temp1,temp2);
beszur(temp2,temp1);

}

for(i=1;i<=n;i++){
	if((a[i]==0)||(!a[i]->lattam)){comp++;a[i]->lattam=true;if(a[i]!=0){bejar(i);}}
}
printf("%d",comp);
return 0;
}