Cod sursa(job #398382)

Utilizator allynaAlina S allyna Data 18 februarie 2010 16:49:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 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 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);
    printf("%d",nrc);
    return 0;
}