Pagini recente » Cod sursa (job #3349140) | Cod sursa (job #2306507) | Cod sursa (job #2552819) | Monitorul de evaluare | Cod sursa (job #3342709)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N=1e5+1;
int n,m,i,j,x,y,sz,low[N],in[N];
bool onStack[N];
vector<int> edge[N],comp[N];
stack<int> s;
void read()
{
fin>>n>>m;
for(i=1;i<=m;++i)
{
fin>>x>>y;
edge[x].push_back(y);
}
}
void pop_stack(int last)
{
sz++;
int x;
do
{
x=s.top();
s.pop();
comp[sz].push_back(x);
onStack[x]=0;
}while(x!=last);
}
void dfs(int x)
{
static int time=0;
in[x]=low[x]=++time;
onStack[x]=1;
s.push(x);
for(auto y:edge[x])
{
if(!in[y])
{
dfs(y);
low[x]=min(low[x],low[y]);
}
else if(onStack[y])
{
low[x]=min(low[x],in[y]);
}
}
if(low[x]==in[x])
pop_stack(x);
}
void parc()
{
for(int i=1;i<=n;++i)
{
if(!in[i]) dfs(i);
}
}
void print()
{
fout<<sz<<'\n';
for(int i=1;i<=sz;++i)
{
for(auto x:comp[i])
fout<<x<<' ';
fout<<'\n';
}
}
int main()
{
read();
parc();
print();
return 0;
}