Cod sursa(job #818573)

Utilizator ericptsStavarache Petru Eric ericpts Data 17 noiembrie 2012 17:44:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <vector>

using namespace std;
vector <int> conex[100010];
bool viz[100010];

void dfs(int nod)
{
    viz[nod] = 1;
    int size = conex[nod].size()-1;
    while(size>=0)
    {
        if(!viz[conex[nod][size]])
            dfs(conex[nod][size]);
        --size;
    }
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int n,m;
    int conexe = 0;
    scanf("%d %d",&n,&m);
    int i;
    int a,b;
    while(m--)
    {
        scanf("%d %d",&a,&b);
        conex[a].push_back(b);
        conex[b].push_back(a);
    }
    for(i=1;i<=n;++i)
    {
        if(!viz[i])
        {
            ++conexe;
            dfs(i);
        }
    }
    printf("%d\n",conexe);
    return 0;
}