Cod sursa(job #2202132)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 7 mai 2018 18:18:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>

using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

const int N = 100001, M = 200002;

int vf[2 * M], ant[2 * M], lst[N], nl(0);

bool viz[N];

void adauga(int a, int b) {
    vf[++nl] = b;
    ant[nl] = lst[a];
    lst[a] = nl;
}

void dfs(int nod) {
    viz[nod] = true;
    int nodc = lst[nod];
    while(nodc != 0) {
        if (!viz[vf[nodc]]) {
            dfs(vf[nodc]);
        }
        nodc = ant[nodc];
    }
}

int main() {
    int n, m, x, y;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> x >> y;
        adauga(x, y);
        adauga(y, x);
    }
    int comp(0);
    for (int i = 1; i <= n; ++i) {
//        int nodc = lst[i];
//        while(nodc != 0) {
//            cout << vf[nodc] << " ";
//            if (!viz[vf[nodc]]) {
//                dfs(vf[nodc]);
//            }
//            nodc = ant[nodc];
//        }
//        cout << "\n";
        if (!viz[i]) {
            ++comp;
            dfs(i);
        }
    }
    cout << comp;
    return 0;
}