Cod sursa(job #3030777)

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

using namespace std;

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

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

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

void read();
void dfs(int x);
void Tarjan();
void afis();

 int main()
 {
     read();
     Tarjan();
     afis();
     return 0;
 }

 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 (int const& 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);
}

void read()
{
    fin >> n >> m;
	G = VVI(n + 1);
	v = inStack = VB(n + 1);
	index = low = VI(n + 1);
	int x, y;
	while (m--)
	{
		fin >> x >> y;
		G[x].push_back(y);
	}

}