Cod sursa(job #1027379)

Utilizator BartieSocaciu Vlad Bartie Data 12 noiembrie 2013 18:51:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

vector <int> V[200001];
int n,m,cnt=0;
bool verif[200001]={false};

void dfs(int k);

int main()
{
    fin>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++){
        fin>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(verif[i]==false){
            dfs(i);
            cnt++;
        }
    fout<<cnt;
    return 0;
}
void dfs(int k)
{
    verif[k]=true;
    for(int i=0;i<V[k].size();i++)
        if(verif[V[k][i]]==false)
            dfs(V[k][i]);
}