Cod sursa(job #974604)

Utilizator 2dorTudor Ciurca 2dor Data 17 iulie 2013 18:10:55
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
//DFS CU STACK
ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int MAXN = 100003;
int n, m, a, b, i, result;

struct nod {
    bool visited;
    stack<int> vecini;//vecinii nodului
}nods[MAXN];//vectorul cu nodurile

void read() {
    fin >> n >> m;
    for (; i < m; ++i) {
        fin >> a >> b; cout << a << ' ' << b << '\n';
        nods[a].vecini.push(b);
        nods[b].vecini.push(a);
    }
}

void go(int i) {
    if (!nods[i].visited) {
        nods[i].visited = true;
        while (!nods[i].vecini.empty()) {
            go(nods[i].vecini.top());
            nods[i].vecini.pop();
        }
    }
}

int main() {
    read();
    for (i = 1; i <= n; ++i) {
        if (!nods[i].visited) {
            ++result;
            go(i);
        }
    }
    fout << result << '\n';
    fin.close();
    fout.close();
    return 0;
}