Cod sursa(job #2795721)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 6 noiembrie 2021 20:33:38
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.24 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.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] << ' ';
        }
    }

    // ctc

    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 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';
        }
    }

    // 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);
    vector<vector<int>> tAd(n + 1);

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

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

    Graph G(n, ad, tAd);
    G.stronglyConnectedComponents();

    return 0;
}