Cod sursa(job #1705396)

Utilizator elninoCristian elnino Data 20 mai 2016 15:13:34
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <fstream>
#include <vector>
#include <list>
#include <stack>

void dfs(int N, int init_node, bool *visited, std::vector<std::list<int> > &adj) {

    std::stack<int> s;
    int curr_node;

    // Adaug nodul initial
    s.push(init_node);
    visited[init_node] = true;

    while (!s.empty()) {

        curr_node = s.top();

        unsigned int count = 0;
        for (std::list<int>::iterator neigh = adj[curr_node].begin(); neigh != adj[curr_node].end(); neigh++) {
            count++;
            if (!visited[*neigh]) {
                s.push(*neigh);
                visited[*neigh] = true;
                break;
            }
            if (count == adj[curr_node].size()) s.pop();
        }
    }
}

int main(int argc, char **argv) {

    std::ifstream input("dfs.in");

    if (!input.is_open()) {
        std::cerr << "Cannot open input file!" << std::endl;
        std::exit(-1);
    }

    std::ofstream output("dfs.out");

    if (!output.is_open()) {
        std::cerr << "Cannot open output file!" << std::endl;
        input.close();
        std::exit(-2);
    }

    // Citire Graph
    int N, M, u, v;
    input >> N >> M;

    std::vector<std::list<int> > adj(N + 1, std::list<int>());

    // DFS
    int init_node = 1;
    bool visited[N + 1];
    std::memset(visited, true, N+1);

    while(input >> u >> v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
        visited[u] = false, visited[v] = false;
    }

    int scc = 0;

    for (int i = 0; i <= N; i++)
        if (!visited[i]) {
            dfs(N, init_node, visited, adj);
            scc++;
        }

    std::cout << scc << std::endl;
    input.close();
    output.close();

    return 0;
}