Cod sursa(job #1561460)

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

int N, M;

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

    scanf("%d %d", &N, &M);
    vector<int> V(N);
    
    int fst, snd;
    int unmarked = N;
    int num = 0;
    
    for(int i = 0; i < M; i++) {
        scanf("%d %d", &fst, &snd);
        
        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;
        }
    }

    printf("%d", num+unmarked);

    return 0;
}