Cod sursa(job #2692929)

Utilizator teofilotopeniTeofil teofilotopeni Data 4 ianuarie 2021 13:06:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <vector>
#include <list>
using namespace std;

struct Nod {
    bool vizitat = false;
    vector <int> from;
};

int main() {
    //freopen("FileIn.txt", "r", stdin);
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    int n, m, x, y, i = 1, total = 0;
    scanf("%d %d", &n, &m);

    vector <Nod> nodes(n + 1);
    list <int> order;

    while (m--) {
        scanf("%d %d", &x, &y);
        nodes[x].from.push_back(y);
        nodes[y].from.push_back(x);
    }

    while (i <= n) {
        order.push_back(i);
        nodes[i].vizitat = true;
        while (!order.empty()) {
            vector <int> act = nodes[order.front()].from;
            while (!act.empty()) {
                if (!nodes[act.back()].vizitat)
                    order.push_back(act.back());
                nodes[act.back()].vizitat = true;
                act.pop_back();
            }
            order.pop_front();
        }
        while (i <= n && nodes[i].vizitat)
            i++;
        total++;
    }
    printf("%d", total);
    return 0;
}