Pagini recente » Cod sursa (job #145225) | Cod sursa (job #859008) | Cod sursa (job #1628900) | Cod sursa (job #2002739) | Cod sursa (job #2272616)
#include <fstream>
#include <queue>
#include <cstring>
#define INF 1000000000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int low[100001],niv[100001],d[100001],n,i,j,lvl,a,b,nr,k;
vector<int> s,sol[100001],v[100001];
void dfs(int nod)
{
int i,vecin;
low[nod]=++lvl;niv[nod]=lvl;
d[nod]=1;
s.push_back(nod);
for(i=0;i<v[nod].size();i++)
{
vecin=v[nod][i];
if(niv[vecin]&&d[vecin])
low[nod]=min(low[nod],niv[vecin]);
if(niv[vecin]==0)
{
dfs(vecin);
low[nod]=min(low[nod],low[vecin]);
}
}
if(niv[nod]==low[nod])
{
++nr;
for(;s.back()!=nod;){sol[nr].push_back(s.back());d[s.back()]=0;s.pop_back();}
sol[nr].push_back(s.back());d[s.back()]=0;s.pop_back();
}
}
int main()
{
fin>>n>>k;
for(i=1;i<=k;i++)
{
fin>>a>>b;
v[a].push_back(b);
}
for(i=1;i<=n;i++)
if(niv[i]==0)
dfs(i);
fout<<nr<<"\n";
for(i=1;i<=nr;i++){for(j=0;j<sol[i].size();j++) fout<<sol[i][j]<<" "; fout<<"\n";}
return 0;
}