Cod sursa(job #3368125)

Utilizator papergodChivu Razvan Gabriel papergod Data 13 octombrie 2026 11:39:09
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.76 kb
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <stack>
#include <fstream>

using namespace std;

struct Nod {
    int n = -1;
    vector<int> Adj;
};

struct Graph {
    vector<Nod> Nodes;
    int edgeCount = 0;

    void SetNodeCount(int n) {
        Nodes.resize(n);
        for (int i = 0; i < n; i++) {
            Nodes[i].n = i;
        }
    }

    int GetNodeCount() {
        return Nodes.size();
    }

    Nod& operator[] (int i) {
        return Nodes[i];
    }

    void AddEdge(int u, int v) {
        Nodes[u].Adj.push_back(v);
        edgeCount++;
    }

    int GetEdgeCount() const {
        return edgeCount;
    }
};

vector<int> bfs(Graph &G, int S) {
    vector<int> res(G.GetNodeCount(), -1);

    queue<int> Q;
    Q.push(S);
    res[S] = 0;

    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();

        for (int i : G[u].Adj) {
            if (res[i] == -1) {
                Q.push(i);
                res[i] = res[u] + 1;
            }
        }
    }

    return res;
}

int dfs(Graph &G) {
    vector<bool> vis(G.GetNodeCount(), false);
    stack<int> S;

    int n = 0;

    for (int i = 0; i < G.GetNodeCount(); i++) {
        if (vis[i]) {
            continue;
        }

        S.push(i);
        vis[i] = true;
        n++;
        while (!S.empty()) {
            int u = S.top();
            S.pop();

            for (int i : G[u].Adj) {
                if (!vis[i]) {
                    S.push(i);
                    vis[i] = true;
                }
            }
        }
    }

    return n;
}

pair<int, int> grarb(Graph &G) {
    int AddCount = -1;
    int RemoveCount = 0;

    int M = G.GetEdgeCount();
    int N = G.GetNodeCount();
    int C = dfs(G);
    RemoveCount = M - N + dfs(G);
    AddCount = C - 1;

    return make_pair(RemoveCount, AddCount);
}

vector<int> berarii2(Graph &G, vector<int> &B) {
    vector<bool> vis(G.GetNodeCount(), false);

    queue<int> Q;

    for (auto b : B) {
        Q.push(b);
        vis[b] = true;

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int i : G[u].Adj) {
                if (!vis[i]) {
                    Q.push(i);
                    vis[i] = true;
                }
            }
        }
    }

    vector<int> res;
    for (int i = 0; i < G.GetNodeCount(); i++) {
        if (!vis[i]) {
            res.push_back(i);
        }
    }

    return res;
}

#define in fin
#define out fout

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

int main() {
    Graph G;
    int N, M;
    in >> N >> M;

    G.SetNodeCount(N);

    while (M--) {
        int u, v;
        in >> u >> v;
        G.AddEdge(u-1, v-1);
    }

    cout << dfs(G) << endl;

    //auto k = grarb(G);
    //out << k.first << endl << k.second << endl;
}