Cod sursa(job #2785420)

Utilizator bubblegumixUdrea Robert bubblegumix Data 18 octombrie 2021 17:42:08
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
const int lim = 1e5 + 5;
vector<int> g[lim];
vector<vector<int>> scc;
vector<int> idx, low;
vector<bool> inS;
stack<int> S;
int n, m;

void tarjan(int nod)
{
	static int index=0;
	idx[nod] = low[nod] = index++;
	S.push(nod), inS[nod] = true;
	for (auto it : g[nod])
		if (idx[it] == -1)
		{
			tarjan(it);
			low[nod] = min(low[nod], low[it]);
		}
		else
			if (inS[it])
				low[nod] = min(low[nod], low[it]);
	if (low[nod] == idx[nod])
	{
		vector<int> partSol;
		int n;
		do {
			partSol.push_back(n = S.top());
			S.pop(),inS[n] = false;

		} while (n != nod);
		scc.push_back(partSol);
	}

}

int main()
{
	//freopen("ctc.in", "r", stdin);


	//freopen("ctc.out", "w", stdout);
	cin >> n >> m;
	idx.resize(n + 1, -1);
	low.resize(n + 1, -1);
	inS.resize(n + 1, false);
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
		if(idx[i]==-1)
			tarjan(i);
	cout << scc.size()<<'\n';
	for (auto it : scc)
	{
		for (auto ij : it)
			cout << ij << " ";
		cout << '\n';
	}
	
}