Pagini recente » Cod sursa (job #2057249) | Statistici Matei Ignuta (Matei_Ignuta) | Monitorul de evaluare | Istoria paginii utilizator/zvon | Cod sursa (job #1686840)
#include <bits/stdc++.h>
using namespace std;
#define FILE_IO
int N, M, K;
int idx;
int indx[50005], instv[50005], low[50005];
vector <int> edg[50005];
vector < vector <int> > scc;
stack <int> stv;
void tarjan(int nod)
{
indx[nod] = ++idx;
low[nod] = idx;
instv[nod] = 1;
stv.push(nod);
for(auto it = edg[nod].begin(); it != edg[nod].end(); it++)
{
int nxt = (*it);
if(!indx[nxt])
{
tarjan(nxt);
low[nod] = min(low[nod], low[nxt]);
}
else if(indx[nxt] && instv[nxt])
low[nod] = min(low[nod], low[nxt]);
}
if(low[nod] == indx[nod])
{
vector <int> ctc;
while(!stv.empty())
{
int nd = stv.top();
ctc.push_back(nd);
stv.pop();
instv[nd] = 0;
if(nd == nod)
break;
}
scc.push_back(ctc);
}
}
int main()
{
#ifdef FILE_IO
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
#endif
scanf("%d%d", &N, &M);
for(int i = 1; i <= M; i++)
{
int x, y;
scanf("%d%d", &x, &y);
edg[x].push_back(y);
}
idx = 0;
for(int i = 1; i <= N; i++)
if(!indx[i])
tarjan(i);
printf("%d\n", scc.size());
for(int i = 0; i < scc.size(); i++, printf("\n"))
for(int j = 0; j < scc[i].size(); j++)
printf("%d ", scc[i][j]);
return 0;
}