Pagini recente » Cod sursa (job #1118570) | Cod sursa (job #914784) | Cod sursa (job #774774) | Cod sursa (job #680024) | Cod sursa (job #2120950)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector <int> G[100005];
vector <int> SOL[100005];
stack <int> s;
int m,n,solsize;
struct
{
int index=0,lowlink=0,isInStack=0;
} v[100005];
void citire()
{
scanf("%d%d",&n,&m);
int aux1,aux2;
for(int i=1; i<=m; i++)
{
scanf("%d%d",&aux1,&aux2);
G[aux1].push_back(aux2);
}
}
int idx=1;
void tarjan(int nod)
{
s.push(nod);
v[nod].index=idx++;
v[nod].lowlink=v[nod].index;
v[nod].isInStack=1;
for(auto it:G[nod])
{
if(v[it].index==0)
{
tarjan(it);
v[nod].lowlink=min(v[nod].lowlink,v[it].lowlink);
}
else
{
if(v[it].isInStack)
{
v[nod].lowlink=min(v[nod].lowlink,v[it].index);
}
}
}
if(v[nod].index==v[nod].lowlink)
{
while(s.top()!=nod&&!s.empty())
{
SOL[solsize].push_back(s.top());
v[s.top()].isInStack=0;
s.pop();
}
SOL[solsize].push_back(nod);
solsize++;
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
for(int i=1;i<=n;i++)
if(v[i].index==0)
tarjan(i);
printf("%d\n",solsize);
for(int i=0;i<solsize;i++)
{
for(auto ii:SOL[i])
printf("%d ",ii);
printf("\n");
}
return 0;
}