Cod sursa(job #605402)

Utilizator cont_de_testeCont Teste cont_de_teste Data 28 iulie 2011 15:45:14
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
# include <cstdio>
# include <vector>
using namespace std;

const char *FIN = "dfs.in", *FOU = "dfs.out";
const int MAX = 100005;

int N, M, sol, VIZ[MAX];
vector <int> G[MAX];

void bfs (int S) {
    VIZ[S] = 1;
    int Q[MAX], st = 0, dr = 0;
    for (Q[++dr] = S; st <= dr; ++st) {
        int X = Q[st];
        for (vector <int> :: iterator i = G[X].begin (); i != G[X].end (); ++i)
            if (VIZ[*i] == 0) {
                Q[++dr] = *i, VIZ[*i] = 1;
            }
    }
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &M);
    for (int i = 1, x, y; i <= M; ++i) {
        scanf ("%d %d", &x, &y);
        G[x].push_back (y);
        G[y].push_back (x);
    }
    for (int i = 1; i <= N; ++i)
        if (VIZ[i] == 0)
            ++sol, bfs (i);
    fprintf (fopen (FOU, "w"), "%d", sol);
}