Cod sursa(job #1561668)

Utilizator geni950814Geni Geni geni950814 Data 4 ianuarie 2016 13:16:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

int N, M;
vector<vector<int>> nodes;

vector<int>& DFS(vector<int>& V, int i) {
    if(!V[i]) {
        V[i] = 1;
        for(int x : nodes[i]) {
            V = DFS(V, x);
        }
    }
    return V;
}



int main() {
    
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    scanf("%d %d", &N, &M);
    vector<int> V(N+1);
    
    int fst, snd;
    //int unmarked = N;
    int num = 0;

    for(int i = 0; i <= N; i++) {
        nodes.push_back(vector<int>(0));
    }

    for(int i = 0; i < M; i++) {
        scanf("%d %d", &fst, &snd);
        nodes[fst].push_back(snd);
        nodes[snd].push_back(fst);
    

       /* 
        if(!V[fst] && !V[snd]) {
            num++;
            V[fst] = V[snd] = num;
            //cout << fst << " and " << snd << " both marked: " << num << endl;
            if(fst != snd) {
                unmarked--;
            }
            unmarked --;
        } else if(V[fst] && !V[snd]) {
            V[snd] = V[fst];
            unmarked--;
            //cout << snd << " marked: " << V[fst] << endl;
        } else if(V[snd] && !V[fst]) {
            V[fst] = V[snd];
            unmarked--;
            //cout << fst << " marked: " << V[snd] << endl;
        }
        */
    }

    for(int i = 1; i <= N; i++) {
        if(!V[i]) {
            num++;
            V = DFS(V, i);
        }
    }

    printf("%d", num);

    return 0;
}