Pagini recente » Cod sursa (job #517856) | Cod sursa (job #2619940) | Cod sursa (job #2552445) | Cod sursa (job #2329543) | Cod sursa (job #2854544)
#include <iostream>
#include <vector>
#define MAXN 100000
using namespace std;
struct node{
vector <int> edges;
bool visited;
};
node graph[MAXN];
static inline void addEdge(int a, int b) {
graph[a].edges.push_back(b);
graph[b].edges.push_back(a);
}
void dfs(int pos) {
int i;
graph[pos].visited = true;
for ( i = 0; i < graph[pos].edges.size(); i++ )
if ( !graph[graph[pos].edges[i]].visited )
dfs(graph[pos].edges[i]);
}
int main() {
FILE *fin, *fout;
fin = fopen("dfs.in", "r");
fout = fopen("dfs.out", "w");
int n, m, a, b, ans, i;
fscanf(fin, "%d%d", &n, &m);
for ( i = 0; i < n; i++ ) {
fscanf(fin, "%d%d", &a, &b);
addEdge(a, b);
}
ans = 0;
for ( i = 0; i < n; i++ ) {
if ( !graph[i].visited ) {
ans++;
dfs(i);
}
}
fprintf(fout, "%d\n", ans);
fclose(fin);
fclose(fout);
return 0;
}