Cod sursa(job #1087696)

Utilizator mihai995mihai995 mihai995 Data 19 ianuarie 2014 19:16:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;

const int N = 1 + 1e5, nil = 0xffffffff;

class Graph{
    int *begin, *buff, *nxt;
    int pos;

public:
    void init(int n, int m){
        n++;

        begin = (int*)malloc(n * sizeof(int));
        memset(begin, nil, n * sizeof(int));

        buff = (int*)malloc(m * sizeof(int));
        nxt = (int*)malloc(m * sizeof(int));
        memset(nxt, nil, m * sizeof(int));

        pos = 0;
    }

    void insert(int x, int y){
        buff[pos] = y;
        nxt[pos] = begin[x];
        begin[x] = pos;
        pos++;
    }

    inline int operator[](int x){
        return buff[x];
    }

    inline int start(int x){
        return begin[x];
    }

    inline int next(int x){
        return nxt[x];
    }

    inline int stop(int x){
        return nil;
    }
};

Graph G;
bool use[N];

ifstream in("dfs.in");
ofstream out("dfs.out");

void dfs(int x){
    use[x] = true;

    for (int it = G.start(x) ; it != G.stop(x) ; it = G.next(it))
        if (!use[ G[it] ])
            dfs( G[it] );
}

int main(){
    int n, m, x, y, ans = 0;

    in >> n >> m;
    G.init(n, 2 * m);

    while (m--){
        in >> x >> y;
        G.insert(x, y);
        G.insert(y, x);
    }

    for (int i = 1 ; i <= n ; i++)
        if (!use[i]){
            dfs(i);
            ans++;
        }
    out << ans << "\n";
    return 0;

}