Cod sursa(job #626524)

Utilizator nbibestNeagu Bogdan Ioan nbibest Data 27 octombrie 2011 14:52:59
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int n,m,i,j,x,y,nr;
short v[100000];

vector<int> a[100000];


int dfs(int k)
{
    int i;

   // printf("-%d\n",k);

    if (v[k]==0)
    {
        v[k]=1;
    for (i=0;i<a[k].size();i++)
    {

        if (v[a[k].at(i)]==0)
        {
            //printf("%d\n",a[k].at(i));
            dfs(a[k].at(i));
            //v[a[k].at(i)]=1;

        }
    }
    }
    return 0;

}


int main()
{

    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    scanf("%d %d",&n,&m);

    for (i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }

    for (i=1;i<=n;i++)
    {
        if (v[i]!=1)
        {
             dfs(i);
             nr++;
        }
    }

    printf("%d",nr);


    return 0;
}