Pagini recente » Cod sursa (job #86996) | Cod sursa (job #223990) | Cod sursa (job #1740607) | Cod sursa (job #578225) | Cod sursa (job #2374327)
#include <bits/stdc++.h>
#define dim int(1e5)+5
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,nivel,comp,vf;
bool seen[dim];
int low[dim],st[dim],lvl[dim];
vector <int> graph[dim],ans[dim];
void Read()
{
f>>n>>m;
for(int i=1;i<=m;++i)
{
int x,y;
f>>x>>y;
graph[x].push_back(y);
}
}
void Dfs(int node)
{
st[++vf]=node;
lvl[node]=low[node]=++nivel;
seen[node]=1;
for(int i=0;i<graph[node].size();++i)
{
int son=graph[node][i];
if(!lvl[son])
{
Dfs(son);
low[node]=min(low[node],low[son]);
}
else
if(seen[son])low[node]=min(low[node],low[son]);
}
if(low[node]==lvl[node])
{
++comp;
do
{
ans[comp].push_back(st[vf]);
seen[st[vf]]=0;
--vf;
}while(vf&&st[vf+1]!=node);
}
}
void Solve()
{
for(int i=1;i<=n;++i)
if(!lvl[i])
Dfs(i);
g<<comp<<'\n';
for(int i=1;i<=comp;++i)
{
for(int j=0;j<ans[i].size();++j)
g<<ans[i][j]<<" ";
g<<'\n';
}
}
int main()
{
Read();
Solve();
return 0;
}