Cod sursa(job #2079694)

Utilizator mariusn01Marius Nicoli mariusn01 Data 1 decembrie 2017 18:36:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

vector<int> L[100010]; /// 100000 e vectori (o matrice cu 100000 de linii goale)
ifstream fin ("dfs.in");
ofstream fout("dfs.out");
int n, m, x, y, sol, p, u, v[100010], i, j, nod, vecin;
int c[100010];
int main () {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        L[x].push_back(y); /// lista de vecini a lui x, adica un vector cu toti vecinii lui x,
                            /// memorati unul langa altul (incapand cu pozitia 0).
        L[y].push_back(x);
    }

    for (i=1;i<=n;i++) {
        if (v[i] == 0) {
            sol ++;

            p = 1;
            u = 1;
            c[1] = i;
            v[i] = 1;
            while (p <= u) {
                nod = c[p];
                for (j=0;j<L[ nod ].size(); j++) {
                    vecin = L[nod][j];
                    if ( v[ vecin ] == 0 ) {
                        u++;
                        c[u] = vecin;
                        v[vecin] = 1;
                    }
                }
                p++;
            }
        }
    }
    fout<<sol;

    return 0;
}