Cod sursa(job #629234)

Utilizator MariusMarius Stroe Marius Data 2 noiembrie 2011 21:47:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#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;
}