Cod sursa(job #1439618)

Utilizator antanaAntonia Boca antana Data 22 mai 2015 20:46:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include<cstdio>
#include<vector>
#include<bitset>
using namespace std;
int n;
bitset<100001>viz;
vector<int>v[100001];
void dfs(int nod)
{
    int c;
    while(v[nod].empty()!=1)
    {
        c=v[nod].back();
        if(viz[c]==1)
            v[nod].pop_back();
        else
        {
            viz[c]=1;
            v[nod].pop_back();
            dfs(c);
        }
    }
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int m,i,j,x,y,nr=0;
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            nr++;
            dfs(i);
        }
    }
    printf("%d", nr);
    return 0;
}