Cod sursa(job #2196534)

Utilizator cristiancreteanuCristian Creteanu cristiancreteanu Data 19 aprilie 2018 17:59:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

void DFS(int src, vector<vector<int>>& adj, vector<bool>& visited) {
    stack<int> dfs;
    int node;
    bool allVisited = false;

    dfs.push(src);
    visited[src] = true;

    while (!dfs.empty()) {
        node = dfs.top();

        allVisited = true;

        for (auto it = adj[node].begin(); it != adj[node].end(); ++it) {
            if (!visited[*it]) {
                visited[*it] = true;
                dfs.push(*it);
                allVisited = false;
                break;
            }
        }


        if (allVisited) {
            dfs.pop();
        }
    }
}

int main() {
    int x, y, N, M, i, conex;

//    ifstream f("../input");
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    f >> N >> M;

    vector<vector<int>> adj(N + 1);
    vector<bool> visited(N + 1, false);
    for (i = 1; i <= M; ++i) {
        f >> x >> y;

        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    conex = 0;
    for (i = 1; i <= N; ++i) {
        if (!visited[i]) {
            DFS(i, adj, visited);
            ++conex;
        }
    }

    g << conex << '\n';

    g.close();
    f.close();

    return 0;
}