Pagini recente » Cod sursa (job #3196418) | Cod sursa (job #938774) | Cod sursa (job #730321) | Cod sursa (job #2233292) | Cod sursa (job #2785420)
#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';
}
}