Pagini recente » Cod sursa (job #1571096) | Cod sursa (job #465286) | Cod sursa (job #106381) | Cod sursa (job #3196122) | Cod sursa (job #1851822)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> v[100010], con;
stack<int> stiva;
bitset<100010> in_stiva;
vector< vector<int> > sol;
int st[100010], dr[100010];
void df(int);
int n,m,x,y,pas;
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
v[x].push_back(y);
}
for(int i=1;i<=n;i++)
if(st[i]==0)
df(i);
int sz_sol = sol.size(), sx;
fout<<sz_sol<<'\n';
for(int i = 0; i< sz_sol; i++)
{
sx = sol[i].size();
for(int j=0; j<sx; j++)
fout<<sol[i][j]<<" ";
fout<<'\n';
}
return 0;
}
void df(int nod)
{
pas++;
st[nod] = dr[nod] = pas;
stiva.push(nod);
in_stiva[nod]=1;
for(auto it:v[nod])
{
if(st[it]==0)
{
df(it);
dr[nod] = min(dr[nod], dr[it]);
}
else
if(in_stiva[it] == 1)
dr[nod] = min(dr[nod], dr[it]);
}
if(st[nod] == dr[nod])
{
con.clear();
int t=stiva.top();
while(t!=nod)
{
con.push_back(t);
in_stiva[t] = 0;
stiva.pop();
t = stiva.top();
}
con.push_back(t);
in_stiva[t] = 0;
stiva.pop();
sol.push_back(con);
}
}