Pagini recente » Cod sursa (job #2665911) | Cod sursa (job #773848) | Cod sursa (job #2858597) | Cod sursa (job #1689662) | Cod sursa (job #2644172)
#include <cstdio>
#include <vector>
using namespace std;
void dfs(vector<vector<int>> &arcs, vector<int> &visited, int currentNode, int compNo) {
visited[currentNode] = compNo;
for(int i=0; i<arcs[currentNode].size(); ++i)
if ( ! visited[arcs[currentNode][i]]){
dfs(arcs, visited, arcs[currentNode][i], compNo);
}
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int n, m, compNo, x, y;
scanf("%d%d", &n, &m);
vector<vector<int>> arcs(n+1);
vector<int> visited(n+1);
for(int i=0; i<m; ++i) {
scanf("%d%d", &x, &y);
arcs[x].push_back(y);
arcs[y].push_back(x);
}
compNo = 0;
for(int i=1; i<=n; ++i)
if (visited[i] == 0) {
++compNo;
dfs(arcs, visited, i, compNo);
}
printf("%d\n", compNo);
return 0;
}