Cod sursa(job #1054304)

Utilizator cosmin004Manolescu Cosmin cosmin004 Data 13 decembrie 2013 18:09:55
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
const int NMAX = 100000;
int n,m,viz[NMAX],cnt;
typedef struct nod
{
    int x;
    nod*urm;
}*g;
g v[NMAX];
void adauga(g &varf,int nr)
{
    g p;
    p=new nod;
    p -> x = nr;
    p -> urm = varf;
    varf = p;
}
void citire()
{
        freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);
    int i,x,y;
    for(i = 1; i <= m; i++)
    {
        scanf("%d %d",&x,&y);
        adauga(v[x],y);
        adauga(v[y],x);
    }
}
void DFS(int nod)
{
    g p;
    viz[nod] = 1;
    for (p = v[nod]; p != NULL; p = p->urm)
        if(!viz[p -> x]) DFS(p -> x);
}
int main()
{
    citire();
    for(int i = 1;i <= n; i++) if(!viz[i]){
                                            cnt++;
                                            DFS(i);
                                            }
    printf("%d\n",cnt);
    return 0;
}