Cod sursa(job #1027320)

Utilizator BartieSocaciu Vlad Bartie Data 12 noiembrie 2013 18:36:05
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 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)
{
    for(int i=1;i<=n;i++)
        if(verif[i]==false)
            for(int j=0;j<V[i].size();j++)
                if(V[i][j]==k){
                    verif[i]=true;
                    dfs(i);
                }
}