Cod sursa(job #2878772)

Utilizator ptudortudor P ptudor Data 27 martie 2022 17:11:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
#include <bits/stdc++.h>
#define dbg(x) if(COND) { cout << #x << "=" << x << "\n"; }
#define dbgv(x) if(COND) { cout << #x << ":\n"; for (auto k: x) cout << k << " "; cout << "\n"; }
#define dbgvm(x) if(COND) { cout << #x << ":\n";int ind = 0; for (auto k: x){cout << ind++ << ":"; for (auto p : k) cout << p << " ";cout << "\n"; } cout << "\n"; }
#define brk(x) if (x) COND = true; else COND = false;
//#define int long long
#define sep if (COND) {cout << "\n--------------------\n";}
using namespace std;

bool COND = true;


#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else // LOCAL
ifstream in("ctc.in");
ofstream out("ctc.out");
#endif

typedef vector<vector<int>> vmat;

vmat scc(vmat g) {
    int n = (int)g.size() - 1;
    //dbg(n);
    vector<int> nodes,viz(n + 1 , 0);

    auto rev = [&](vmat &g) {
        vmat revg(n + 1);
        for (int i = 1; i <= n; i++) {
            for (auto k : g[i]) {
                revg[k].push_back(i);
            }
        }
        g = revg;
    };
   // dbgvm(g);
       vmat components;

    function<void(int,bool)> dfs = [&](int node, bool flag) {
        if (flag == true) {
            components[(int)components.size() - 1].push_back(node);
        }
        viz[node] = 1;
        for (auto k : g[node]) {
              //  dbg(k);
            if (viz[k] == 0) {
                viz[k] = 1;
                dfs(k , flag);
            }
        }
        if (flag == false) {
            nodes.push_back(node);
        }
    };


    for (int i = 1; i <= n; i++) {
        if (viz[i] == 0)
        dfs(i , false);
    }
    rev(g); /// reverses the graph
//
  //  dbgv(nodes);

    viz = vector<int> (n + 1, 0);
    for (int i = (int)nodes.size() - 1; i >= 0; i--) { /// nodes keeps the nodes in reverse order of tout
        int l = nodes[i];
        if (viz[l] == 0) {
            components.push_back({});
            dfs(l , true);
        }
    }

    //dbgvm(components);

    return components;
}
int32_t main() {
    int n,m;
    in >> n >> m;
    vmat g(n + 1);

    for (int i = 1; i <= m; i++) {
        int u,v;
        in >> u >> v;
        g[u].push_back(v);
    }
    vmat components = scc(g);
    out << components.size() << "\n";
    for (auto k : components) {
        for (auto p : k) {
            out << p << " ";
        }
        out << "\n";
    }
}