Pagini recente » Cod sursa (job #737769) | Cod sursa (job #591072) | Cod sursa (job #1751981) | Cod sursa (job #1562943) | Cod sursa (job #1383278)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 100004
vector<int> adj[2 * MAXN];
vector<bool> visited(MAXN, false);
void bfs(int node) {
visited[node] = true;
int v_size = adj[node].size();
for(int i = 0; i < v_size; ++i) {
if(visited[adj[node][i]] == false) {
bfs(adj[node][i]);
}
}
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N,M; fin >> N >> M;
for(int i = 0; i < N; ++i) {
int node1, node2; fin >> node1 >> node2;
adj[node1].push_back(node2);
adj[node2].push_back(node1);
}
int components = 0;
for(int i = 1; i <= N; ++i) {
if(visited[i] == false) {
++components;
bfs(i);
}
}
fout << components << "\n";
return 0;
}