Cod sursa(job #384881)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 21 ianuarie 2010 17:30:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<cstdio>
#include<fstream>
using namespace std;
struct nod{
int info;
nod *next;
};
nod *a[100005];
int n,m,nrc=0,v[100005];

void citire()
{
    freopen("dfs.in","r",stdin);
    scanf("%d%d", &n, &m);
    int i,x,y;
    nod  *p;
    for(i=1;i<=n;i++)
        a[i]=NULL;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d", &x, &y);
        p=new nod;
        p->info=y;
        p->next=a[x];
        a[x]=p;
        p=new nod;
        p->info=x;
        p->next=a[y];
        a[y]=p;
    }
}

void write()
{
    int i;
    for(i=1;i<=n;i++)
    {
        printf("%d: ",i);
        for(nod *p=a[i];p;p=p->next)
            printf("%d ", p->info);
        printf("\n");
    }
}

void dfs(int varf, int nrc)
{
    v[varf]=nrc;
    for(nod *p=a[varf];p;p=p->next)
        if(v[p->info]==0)
            dfs(p->info,nrc);
}


int main()
{
    int i;
    citire();
    for(i=1;i<=n;i++)
        if(v[i]==0)
            dfs(i,++nrc);
    freopen("dfs.out","w",stdout);
    //write();
    printf("%d",nrc);
    return 0;
}