Cod sursa(job #3030717)

Utilizator Vincent47David Malutan Vincent47 Data 17 martie 2023 20:27:31
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");

 using VI = vector<int>;
 using VB = vector<bool>;
 using VVI = vector<VI>;

 int indx, n, m;
 VB v, inStack;
 VI index, low;
 VVI G;
 set<int> cc;
 set<set<int> > ctc;
 stack<int>stk;

 int extract(int x)
 {
     cc.clear();
     while(!stk.empty())
     {
         int node = stk.top();
         stk.pop();
         inStack[node] = 0;
         cc.insert(node);
         if (node == x)
            break;
     }
     ctc.insert(cc);
 }

 void dfs(int x)
 {
     v[x] = 1;
     stk.push(x);
     index[x] = low[x] = ++ indx;
     inStack[x] = 1;

     for (auto y : G[x])
     {
         if (!v[y]) {
            dfs(y);
            low[x] = min(low[y], low[x]);
         }
         else if (inStack[y])
            low[x] = min(index[y], low[x]);
     }
     if (index[x] == low[x])
        extract(x);
 }

 void afis()
 {
     cout << ctc.size() << '\n';
     for (auto cc : ctc) {
        for (auto j : cc)
        cout << j << ' ';
     cout << '\n';
     }
 }

 int main()
 {
     cin >> n >> m;
     int x, y;
     G = VVI(n + 1);
     v = VB(n + 1);
     inStack = VB(n + 1);
     index = low = VI(n + 1);
     for (int i = 1; i <= m; ++i)
     {
         cin >> x >> y;
         G[x].push_back(y);
     }
     for (int i = 1; i <= n; ++i)
        if (!v[i])
        dfs(i);

     afis();
     return 0;
 }