Cod sursa(job #155953)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 12 martie 2008 11:44:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#define vv 100001

using namespace std;

struct nod
    {
        int val;
        nod *next;
    };

int n,m,v[vv];
nod *a[vv];

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

void dfs(int w)
{
    for (nod *p=a[w]; p; p=p->next)
        if (!v[p->val])
        {
            v[p->val]=1;
            dfs(p->val);
        }
}

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