Cod sursa(job #3030761)

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

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

 using VI = vector<int>;
 using VB = vector<bool>;
 using VVI = vector<VI>;
 using SI = set<int>;
 using SSI = set<SI>;

 int indx, n, m;
 VB v, inStack;
 VI index, low;
 VVI G;
 SI cc;
 SSI 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 (const int& 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()
 {
     fout << ctc.size() << '\n';
     for (auto cc : ctc) {
        for (int j : cc)
        fout << j << ' ';
     fout << '\n';
     }
 }
 void Tarjan()
{
	for (int node = 1; node <= n; ++node)
		if (!v[node])
			dfs(node);
}


 int main()
 {
     fin >> 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)
     {
         fin >> x >> y;
         G[x].push_back(y);
     }
     Tarjan();
     afis();
     return 0;
 }