Cod sursa(job #1033503)

Utilizator Master011Dragos Martac Master011 Data 17 noiembrie 2013 00:50:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<cstdio>
#include<vector>

using namespace std;
const int Lim = 100001;
vector<int> v[Lim];
int sol, Nod[Lim];

void dfs(int start){
    Nod[start] = 1;
    for (int i = 0; i < v[start].size() ; ++i)
        if (!Nod[v[start][i]])
            dfs(v[start][i]);
}

int main(){
    FILE *in = fopen("dfs.in","r");
    FILE *out = fopen("dfs.out","w");

    int N,M,a,b; fscanf(in,"%d%d",&N,&M);
    for(int i = 1 ; i <= M ; ++i){
        fscanf(in,"%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i = 1 ; i <= N ; ++i){
        if(!Nod[i]){
            dfs(i);
            ++sol;
        }
    }

    fprintf(out,"%d\n",sol);
    fclose(in);
    fclose(out);
    return 0;
}