Cod sursa(job #944384)

Utilizator avramavram andrei marius avram Data 28 aprilie 2013 12:43:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb

#include <fstream>
#include <vector>

using namespace std;
#define DIM 100010


vector<int> L[DIM];
vector<int>::iterator it;

int c[DIM];
int v[DIM];

int n, m, k, i, j, s, p, u, prim, nc;

void coada(int s) {
    c[1] = s;
    v[s] = 1;
    p = 1;
    u = 1;

    while (p<=u) {
        // analizez vecinii nevizitati ai lui c[p]
        prim = c[p];
        for (it = L[prim].begin(); it!= L[prim].end(); it++) {
            if (v[ *it ] == 0) {
                u++;
                c[u] = *it;
                v[*it] = v[prim] + 1;
            }
        }
        p++;

    }
}

int main() {
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    fin >> n>>m;
    for (k=1;k<=m;k++) {
        fin>>i>>j;
        // adaugam elementul j in lista lui i
        L[i].push_back(j);
        L[j].push_back(i);
//        a[i][j] = 1;
    }


    for (i=1;i<=n;i++)
        if (v[i] == 0) {
            coada(i);
            nc++;
        }
    fout<<nc<<"\n";
    return 0;
}