Cod sursa(job #469679)

Utilizator vlad.maneaVlad Manea vlad.manea Data 8 iulie 2010 16:24:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream.h>
#include <queue>
using namespace std;

#define nmax (100005)

int N, M, A;
int *G[nmax];
bool Viz[nmax];
queue<int> Q;

// read data

void read() {

    // read graph size
    ifstream fin("dfs.in");
    fin >> N >> M;

    // prepare lists
    for (int i = 1; i <= N; ++i) {
        G[i] = (int*) malloc(sizeof (int));
        G[i][0] = 0;
    }

    // read degrees
    while (M--) {
        int x, y;
        fin >> x >> y;
        G[x][0]++;
        G[y][0]++;
    }
    fin.close();

    // prepare lists for incoming degrees
    for (int i = 1; i <= N; ++i) {
        G[i] = (int*) realloc(G[i], (G[i][0] + 1) * sizeof (int));
        G[i][0] = 0;
    }

    // read actual vertices
    ifstream fim("dfs.in");
    fim >> N >> M;
    while (M--) {
        int x, y;
        fim >> x >> y;
        G[x][++G[x][0]] = y;
        G[y][++G[y][0]] = x;
    }
    fim.close();

}

// solve task

void solve() {

    for (int k = 1; k <= N; ++k) {
        if (!Viz[k]) {
            ++A;
            Viz[k] = 1;
            for (Q.push(k); !Q.empty(); Q.pop()) {
                int v = Q.front();
                for (int i = 1; i <= G[v][0]; ++i) {
                    int w = G[v][i];
                    if (!Viz[w]) {
                        Viz[w] = 1;
                        Q.push(w);
                    }
                }
            }
        }
    }

}

// write data

void write() {

    // write array
    ofstream fout("dfs.out");
    fout << A << '\n';
    fout.close();

}

int main() {

    read();
    solve();
    write();
    return 0;

}