Pagini recente » Cod sursa (job #1303563) | Cod sursa (job #1963611) | Cod sursa (job #1315792) | Cod sursa (job #1503019) | Cod sursa (job #1491387)
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, k;
struct node{
node *next;
int inf;
};
node *V[100005];
int viz[100005];
void add(node *&start, int inf) {
node *one = new node;
one->inf = inf;
one->next = start;
start = one;
}
void bfs(int in) {
queue<int> q;
q.push(in);
viz[in] = k;
while(!q.empty()) {
in = q.front();
q.pop();
for(node *p = V[in]; p; p = p->next) {
if(!viz[p->inf]) {
q.push(p->inf);
viz[p->inf] = k;
}
}
}
}
int main()
{
FILE *f = fopen("dfs.in", "r");
FILE *g = fopen("dfs.out", "w");
fscanf(f, "%d %d", &n, &m);
for(int i = 1; i <= m; i ++) {
fscanf(f, "%d %d", &x, &y);
add(V[x], y);
add(V[y], x);
}
for(int i = 1; i <= n; i ++) {
if(!viz[i]) {
k ++;
bfs(i);
}
}
fprintf(g, "%d\n", k);
return 0;
}