Pagini recente » Cod sursa (job #2687916) | Cod sursa (job #3237753) | Cod sursa (job #3278918) | Cod sursa (job #3132589) | Cod sursa (job #2961033)
#include<bits/stdc++.h>
using namespace std;
const int maxN = (1e5)+5;
vector<int> v[maxN];
int niv[maxN],low[maxN];
int st[maxN],vf;
bool inStack[maxN];
vector<int> C[maxN];
int ctc;
int lvl;
void dfs(int nod)
{
lvl++;
niv[nod] = lvl;
low[nod] = lvl;
st[++vf] = nod;
inStack[nod] = 1;
for(auto it:v[nod])
{
if(!niv[it])
{
dfs(it);
low[nod] = min(low[nod],low[it]);
}
else
if(inStack[it])
{
low[nod] = min(low[nod],low[it]);
}
}
if(low[nod]==niv[nod])
{
ctc++;
while(vf>0 && st[vf]!=nod)
{
C[ctc].push_back(st[vf]);
inStack[st[vf]] = 0;
vf--;
}
C[ctc].push_back(st[vf]);
inStack[st[vf]] = 0;
vf--;
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m;
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
v[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
if(!niv[i])
dfs(i);
}
fout<<ctc<<'\n';
for(int i=1;i<=ctc;i++)
{
for(auto it:C[i])
fout<<it<<' ';
fout<<'\n';
}
return 0;
}