Cod sursa(job #1446664)

Utilizator relu.draganDragan Relu relu.dragan Data 2 iunie 2015 15:54:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
void dfs(vector<vector<int> >& v, int i, vector<int>& viz)
{
    viz[i] = 1;
    for (int j = 0; j < v[i].size(); j++){

        if (viz[v[i][j]] == 0){
           // printf("%d %d\n", i, v[i][j]);
            dfs(v,v[i][j],viz);
        }
    }
}
int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int N,M,a,b,nr = 0;

    f >> N >> M;
    vector<vector<int> > v(N+1);
    for (int i = 0; i < M; i ++){
        f >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    /*for (int i = 1; i < N; i++){
        printf("%d: ",i);
        for (int j = 0; j < v[i].size(); j ++)
            printf("%d, ", v[i][j]);
        printf("\n");
    }*/
    vector<int> viz(N+1,0); 
    for (int i = 1; i < N+1 ; i++){
        if (viz[i] == 0){
            nr++;
            dfs(v,i,viz);
           /* printf("vizitat: ");
            for (int j = 1 ; j < viz.size(); j++)
                printf("%d ", viz[j]);
            printf("\n");*/
        }

    }
    g << nr;
    f.close();
    g.close();
    return 0;
}