Cod sursa(job #1087665)

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

const int N = 1 + 1e8;

class Graph{ ///WORKS WITH |V| < 2 ^ 21
    long long* buff;
    int *vect, *grad;
    int nrV, pos, posM;
    bool UnOriented;

    void addInt(long long x){
        buff[pos] ^= x << posM;
        posM += 21;
        if (posM == 63){
            posM = 0;
            pos++;
        }
    }

    int getInt(){
        if (posM == 0){
            posM = 42;
            pos--;
        } else
            posM -= 21;
        return ( buff[pos] >> posM ) & ((1 << 21) - 1);
    }
public:
    void init(int n, int m, bool UnOr){
        UnOriented = UnOr;
        nrV = n;
        buff = (long long*)malloc( (1 + 2 * m / 3) * sizeof(long long) );
        memset(buff, 0, (1 + 2 * m / 3) * sizeof(long long));
        if (UnOriented) m <<= 1;
        vect = (int*)malloc(m * sizeof(int));
        grad = (int*)malloc((n + 2) * sizeof(int));
        memset(grad, 0, (n + 2) * sizeof(int));
        pos = posM = 0;
    }

    void insert(int x, int y){
        addInt(x); addInt(y);
        grad[x]++;
        if (UnOriented) grad[y]++;
    }

    void build(){
        for (int i = 1 ; i <= nrV + 1 ; i++)
            grad[i] += grad[i - 1];

        if (UnOriented){
            int x, y;
            while (pos || posM){
                y = getInt();
                x = getInt();
                vect[ --grad[x] ] = y;
                vect[ --grad[y] ] = x;
            }
        } else
            while (pos || posM)
                vect[ grad[ getInt() ]++ ] = getInt();
        free(buff);
    }

    inline int* start(int x){
        return vect + grad[x];
    }

    inline int* stop(int x){
        return vect + grad[x + 1];
    }
};

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++)
        if (!use[*it])
            dfs(*it);
}

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

    in >> n >> m;
    G.init(n, m, 1);

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

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

}