Cod sursa(job #956888)

Utilizator cousin.batmanVaru Batman cousin.batman Data 3 iunie 2013 23:30:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream>
#include<vector>
#include<list>

using namespace std;

vector< bool > v;
vector< list<int> > edges;

void dfs(int s){
    int x;
    list<int> q;
    q.push_back(s);

    while(q.size()){
        x = q.front(), q.pop_front();
        for(auto it=edges[x].begin(); it!=edges[x].end(); it++){
            if(!v[*it]) v[*it]=true, q.push_back(*it);
        }
    }
    
}

int main(){
    int count=0, n, m, x, y, i;
    freopen("dfs.in", "rt", stdin);
    freopen("dfs.out", "wt", stdout);
    
    scanf("%d %d", &n, &m);
    edges.resize(n+1), v.resize(n+1, false);

    for(i=0; i<m ;i++){
        scanf("%d %d", &x, &y);
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    for(i=1; i<=n; i++)
        if(!v[i]) dfs(i), count++;

    printf("%d\n", count);

    fclose(stdin);
    fclose(stdout);
    return 0;
}