Cod sursa(job #1923197)

Utilizator HoriaDruliacHoria Druliac HoriaDruliac Data 10 martie 2017 21:20:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <cstdio>
#include <bitset>
#include <vector>
#define VAL 100005

using namespace std;     /// Varianta 2 ... de 100 pct cu Vector de adj.

int N,M,a,b,ans,i;
bitset<VAL> ok;
vector<int> v[VAL] ;

void citire()
{
    int i;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&N,&M);
    for(i=1; i<=M; i++)
    {
        scanf("%d %d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
}
void dfs(int b)
{
    vector<int>:: iterator it;
    ok[b]=1;
    for(it=v[b].begin(); it!=v[b].end(); it++)
        if(!ok[*it])
            dfs(*it);
}
int main()
{
    citire();
    for(i=1; i<=N; i++)
        if(!ok[i])
        {
            ++ans;
            dfs(i);
        }
    printf("%d",ans);
    return 0;
}