Pagini recente » Cod sursa (job #526267) | Cod sursa (job #1983378) | Cod sursa (job #1617703) | Cod sursa (job #1403753) | Cod sursa (job #1561668)
#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;
}