Pagini recente » Cod sursa (job #372631) | Cod sursa (job #726636) | Cod sursa (job #684197) | Cod sursa (job #2835534) | Cod sursa (job #928451)
Cod sursa(job #928451)
#include<fstream>
#include<vector>
using namespace std;
vector <int> a[100001],v,s;
vector <vector <int> > sol;
int d[100001],l[100001],n,m,i,j,x,y,p;
bool w[100001];
void df(int x)
{
int i,y;
d[x]=l[x]=++p;
s.push_back(x);
w[x]=1;
for (i=0;i<a[x].size();i++)
{
y=a[x][i];
if (l[y]==0)
{
df(y);
d[x]=min(d[x],d[y]);
}
else if (w[y]==1)
d[x]=min(d[x],l[y]);
}
if (d[x]==l[x])
{
v.resize(0);
while (s.back()!=x)
{
v.push_back(s.back());
w[s.back()]=0;
s.pop_back();
}
v.push_back(s.back());
s.pop_back();
sol.push_back(v);
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
f >> n >> m;
for (i=1;i<=m;i++)
{
f >> x >> y;
a[x].push_back(y);
}
for (i=1;i<=n;i++)
if (l[i]==0)
df(i);
g << sol.size() << "\n";
for (i=0;i<sol.size();i++)
{
for (j=0;j<sol[i].size();j++)
g << sol[i][j] << ' ';
g << "\n";
}
return 0;
}