Pagini recente » Cod sursa (job #2331892) | Monitorul de evaluare | Istoria paginii runda/wellcodesimulareav-10martie | Cod sursa (job #2847531) | Cod sursa (job #2200142)
#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,howmany;
vector<int>nod[100005];
bitset<100005>ap,stk;
stack<int>s;
vector<vector<int> >ans;
int val[100005];
void go_visit(int pos)
{
if(val[pos]==0)
val[pos]=++howmany;
int cop=val[pos];
ap[pos]=1;
stk[pos]=1;
s.push(pos);
for(int i=0;i<nod[pos].size();i++)
{
if(ap[nod[pos][i]])
{
if(stk[nod[pos][i]]==1)
val[pos]=min(val[pos],val[nod[pos][i]]);
}
else
{
go_visit(nod[pos][i]);
val[pos]=min(val[pos],val[nod[pos][i]]);
}
}
if(cop==val[pos])
{
vector<int>which;
int nod=0;
while(nod!=pos)
{
which.push_back(s.top());
nod=s.top();
stk[nod]=0;
s.pop();
}
ans.push_back(which);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d\n",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d\n",&x,&y);
nod[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
if(ap[i])
continue;
go_visit(i);
}
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++)
{
for(int j=0;j<ans[i].size();j++)
printf("%d ",ans[i][j]);
printf("\n");
}
return 0;
}