Pagini recente » Cod sursa (job #2799970) | Cod sursa (job #2096719) | Cod sursa (job #740171) | Cod sursa (job #998278) | Cod sursa (job #1450973)
#include <iostream>
#include <vector>
#include <list>
#include <bitset>
const int NMAX = 100001;
const char IN[] = "dfs.in", OUT[] = "dfs.out";
using namespace std;
list<int> G[NMAX];
int N, M;
inline void readData() {
freopen(IN, "r", stdin);
scanf("%d %d", &N, &M);
for (int i = 0; i < M; ++i) {
int src, dst;
scanf("%d %d", &src, &dst);
G[src].push_back(dst);
G[dst].push_back(src);
}
fclose(stdin);
}
bitset<NMAX> visited;
void DFS(int node) {
visited[node].flip();
for (auto& n : G[node]) {
if (!visited[n]) DFS(n);
}
}
int main() {
readData();
int CC_count = 0;
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
DFS(i);
++CC_count;
}
}
fprintf(fopen(OUT, "w"), "%d\n", CC_count);
return 0;
}