Pagini recente » Cod sursa (job #2737381) | Cod sursa (job #1974808) | Cod sursa (job #3155711) | Cod sursa (job #3171935) | Cod sursa (job #629234)
Cod sursa(job #629234)
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const char iname[] = "dfs.in";
const char oname[] = "dfs.out";
const int MAX_N = 100000;
vector <int> adj[MAX_N], visited;
void go(int node) {
queue <int> que;
que.push(node), visited[node] = true;
while (!que.empty()) {
int u = que.front();
que.pop();
vector <int>::iterator it;
for (it = adj[u].begin(); it != adj[u].end(); ++ it) {
if (!visited[*it]) {
visited[*it] = true;
que.push(*it);
}
}
}
}
int main(void ) {
FILE *fi = fopen(iname, "r");
int nodes, edges;
fscanf(fi, "%d %d", &nodes, &edges);
for (int i = 0; i < edges; ++ i) {
int u, v;
fscanf(fi, "%d %d", &u, &v);
adj[u - 1].push_back(v - 1);
adj[v - 1].push_back(u - 1);
}
fclose(fi);
visited.resize(nodes);
visited.assign(visited.size(), false);
int ans = 0;
for (int i = 0; i < nodes; ++ i) if (!visited[i]) {
go(i);
ans ++;
}
fprintf(fopen(oname, "w"), "%d", ans);
return 0;
}