Cod sursa(job #1623480)

Utilizator pringonGoje Samuel Andrei Daniel pringon Data 1 martie 2016 19:46:27
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

using namespace std;

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

int m, n, nr = 1, t, lst[200000], vf[400000], urm[400000];
bool viz[100000];

void adauga(int x, int y) {
    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void citire() {
    int temp1, temp2;
    for(int i=1;i<=n;i++) {
        lst[i] = i;
    }
    for(int i=1;i<=m;i++) {
        in>>temp1>>temp2;
        adauga(temp1, temp2);
        adauga(temp2, temp1);
    }
}

void dfs(int x) {
    viz[x] = true;
    int p, y;
    p = lst[x];
    while(p!=0) {
        y = vf[p];
        if(!viz[y]){
            dfs(y);
            }
        p = urm[p];
    }
}

int main() {
    in>>n>>m;
    citire();
    for(int i=1;i<=n;i++) {
        if(!viz[i]) {
            t++;
            dfs(i);
        }
    }
    out<<t;

    in.close();
    out.close();
    return 0;
}