Cod sursa(job #2796632)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 8 noiembrie 2021 16:17:29
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.18 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

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

class Graph {
public:
    // dfs

    void DFS(int v, vector<bool> &vis) {
        vis[v] = true;

        for (auto &x : m_ad[v]) {
            if (!vis[x]) {
                DFS(x, vis);
            }
        }
    }

    int components() {
        int compCount = 0;
        vector<bool> vis(m_n, false);

        for (int i = 1; i <= m_n; ++i) {
            if (!vis[i]) {
                ++compCount;
                DFS(i, vis);
            }
        }

        return compCount;
    }

    // bfs

    void minDist(int start) {
        vector<int> dist(m_n + 1, -1);
        queue<int> Q;
        int x;

        dist[start] = 0;
        Q.push(start);

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

            for (auto &y : m_ad[x]) {
                if (dist[y] == -1) {
                    dist[y] = dist[x] + 1;
                    Q.push(y);
                }
            }
        }

        for (int i = 1; i <= m_n; ++i) {
            fout << dist[i] << ' ';
        }
    }

    // sortare topologica

    void topologicalSort(int v, vector<bool> &vis, vector<int> &stack) {
        vis[v] = true;

        for (auto &x : m_ad[v]) {
            if (!vis[x]) {
                topologicalSort(x, vis, stack);
            }
        }

        stack.push_back(v);
    }

    void printTopoSorted() {
        vector<bool> vis(m_n + 1, false);
        vector<int> stack;

        for (int i = 1; i <= m_n; ++i) {
            if (!vis[i]) {
                topologicalSort(i, vis, stack);
            }
        }

        for (int i = stack.size() - 1; i >= 0; --i) {
            fout << stack[i] << ' ';
        }
    }

    // ctc

    void tDFS(int v, vector<bool> &vis, int compCount, vector<vector<int>> &comp) {
        vis[v] = true;
        comp[compCount - 1].push_back(v);

        for (auto &x : m_tAd[v]) {
            if (!vis[x]) {
                tDFS(x, vis, compCount, comp);
            }
        }
    }

    void stronglyConnectedComponents() {
        vector<bool> vis1(m_n + 1, false);
        vector<bool> vis2(m_n + 1, false);
        vector<int> stack;
        int compCount = 0;
        vector<vector<int>> comp;

        for (int i = 1; i <= m_n; ++i) {
            if (!vis1[i]) {
                topologicalSort(i, vis1, stack);
            }
        }

        for (int i = stack.size() - 1; i >= 0; --i) {
            if (!vis2[stack[i]]) {
                ++compCount;
                comp.emplace_back();
                tDFS(stack[i], vis2, compCount, comp);
            }
        }

        fout << compCount << '\n';

        for (int i = 0; i < compCount; ++i) {
            for (auto &x : comp[i]) {
                fout << x << ' ';
            }

            fout << '\n';
        }
    }

    // biconex

    void bccDFS(int v, int parent, vector<int> &disc, vector<int> &low,
                vector<int> &stack, vector<vector<int>> &comp) {
        static int time = 0;
        int children = 0;
        disc[v] = low[v] = ++time;

        for (auto &w : m_ad[v]) {
            if (w == parent) continue; // (w, v) e muchie de intoarcere

            if (!disc[w]) {
                ++children;
                stack.push_back(w);
                bccDFS(w, v, disc, low, stack, comp);
                low[v] = min(low[v], low[w]);

                if (low[w] >= disc[v]) {
                    comp.emplace_back();
                    stack.push_back(v);

                    while (!stack.empty() && stack.back() != w) {
                        comp[comp.size() - 1].push_back(stack.back());
                        stack.pop_back();
                    }

                    if (!stack.empty()) {
                        comp[comp.size() - 1].push_back(stack.back());
                        stack.pop_back();
                    }
                }
            } else if (w != parent) {
                low[v] = min(low[v], disc[w]);
            }
        }
    }

    void biconnectedComponents() {
        vector<int> disc(m_n + 1, 0);
        vector<int> low(m_n + 1, 0);
        vector<int> stack;
        vector<vector<int>> comp;

        bccDFS(1, 0, disc, low, stack, comp);

        fout << comp.size() << '\n';

        for (auto &c : comp) {
            for (auto &v : c) {
                fout << v << ' ';
            }

            fout << '\n';
        }
    }

    // constructori

    Graph(int n, vector<vector<int>> &ad) :
        m_n(n), m_ad(ad), m_tAd() {}
    Graph(int n, vector<vector<int>> &ad, vector<vector<int>> &tAd) :
        m_n(n), m_ad(ad), m_tAd(tAd) {}

private:
    int m_n;
    vector<vector<int>> m_ad;
    vector<vector<int>> m_tAd;
};

int main() {
    int n, m, x, y;

    fin >> n >> m;

    vector<vector<int>> ad(n + 1);

    for (int i = 1; i <= m; ++i) {
        fin >> x >> y;

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

    Graph G(n, ad);
    G.biconnectedComponents();

    return 0;
}