Cod sursa(job #1471186)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 13 august 2015 13:45:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.56 kb
#include<stdio.h>
#include<stdlib.h>
int a[300003],b[300003],*g[100001],w[100001],n,m,i,t,c[100001];
void D(int i) {
	c[i]=1;
	for(int j=0;j<w[i];j++)
	if(!c[g[i][j]])
    	D(g[i][j]);
}
int main() {
	freopen("dfs.in","r",stdin),freopen("dfs.out","w",stdout),scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
    	scanf("%d%d",&a[i],&b[i]),w[a[i]]++,w[b[i]]++;
	for(i=1;i<=n;w[i++]=0)
    	g[i]=(int*)malloc(w[i]*sizeof(int));
	for(i=1;i<=m;i++)
    	g[a[i]][w[a[i]]++]=b[i],g[b[i]][w[b[i]]++]=a[i];
	for(i=1;i<=n;i++)
	if(!c[i])
    	D(i),t++;
	printf("%d",t);
}