Cod sursa(job #1492832)

Utilizator DobosDobos Paul Dobos Data 28 septembrie 2015 11:39:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
const int MAX = 1e5 + 5;
vector < int > q[MAX];
bitset < MAX > v;
void dfs(int x)
{
    v[x] = 1;
    for(int i = 0 ; i < q[x].size(); i++){
    if(!v[q[x][i]]){
        dfs(q[x][i]);
    }
    }
}


int main()
{
    int n, m ,x,y;
    fin >> n >> m ;
    for(int i = 0; i < m; i++){
        fin >> x >> y;
        q[x].push_back(y);
        q[y].push_back(x);
    }
    int cp  = 0;
    for(int i = 1; i <= n; i++){
        if(!v[i]){
            dfs(i);
            cp++;
        }
    }
   fout << cp;
    return 0;
}