Cod sursa(job #534128)

Utilizator SadmannCornigeanu Calin Sadmann Data 15 februarie 2011 11:50:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>
FILE *in=fopen("dfs.in","rt");
FILE *out=fopen("dfs.out","wt");

typedef struct nod
{
    int x;
    nod *a;
} *pNod;
pNod v[100005];

void add(pNod &dest, int val)
{
	pNod p;
	p = new nod;
	p -> x = val;
	p -> a = dest;
	dest = p;
}

void DFS(int nod);


int n,m,x,y,cnt,i,viz[100005];

int main()
{
    fscanf(in,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d %d",&x,&y);
        add(v[x],y);
        add(v[y],x);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
        {
            cnt++;
            DFS(i);
        }
    fprintf(out,"%d",cnt);

    return 0;
}
void DFS(int nod)
{
    pNod p;
    viz[nod]=1;
    for(p=v[nod];p!=NULL;p=p->a)
        if(!viz[p->x])
            DFS(p->x);
}