Pagini recente » Cod sursa (job #2037670) | Cod sursa (job #808834) | Cod sursa (job #1743920) | Clasament simulare-cartita-31b | Cod sursa (job #2432470)
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <vector>
void dfs(int src, std::vector<bool> &visited, std::vector<int> *adj) {
visited[src] = true;
for (int i = 0 ; i < adj[src].size() ; ++i) {
if (!visited[adj[src][i]]) {
visited[adj[src][i]] = true;
dfs(adj[src][i], visited, adj);
}
}
}
int get_nr_components(int src, std::vector<bool> &visited, std::vector<int> *adj, int &N) {
int counter = 0;
for (int i = 1 ; i <= N ; ++i) {
if (!visited[i]) {
++counter;
visited[i] = true;
dfs(i, visited, adj);
}
}
return counter;
}
int main() {
int N, M, src, dest;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d%d", &N, &M);
assert(1 <= N && N <= 100000);
std::vector<int> *adj = new std::vector<int>[N + 1];
std::vector<bool> visited(N + 1, false);
for (; M; --M) {
scanf("%d %d", &src, &dest);
adj[src].push_back(dest);
adj[dest].push_back(src);
}
int counter = get_nr_components(src, visited, adj, N);
printf("%d\n", counter);
delete [] adj;
return 0;
}