Pagini recente » Cod sursa (job #2483373) | Cod sursa (job #1870026) | Cod sursa (job #3037896) | Cod sursa (job #2616150) | Cod sursa (job #1646340)
#include <fstream>
#include <vector>
#define w 100001
using namespace std;
int ll[w];
int st[w];
bool onst[w];
int idx[w];
int p,index=1,nr;
vector <int> a[w];
vector <int> rez[w];
void tarjan(int x)
{
idx[x]=index;
ll[x]=index;
index++;
st[++p]=x;
onst[x]=1;
int i,y;
for (i=0;i<a[x].size();i++)
{
y=a[x][i];
if (!idx[y])
{
tarjan(y);
ll[x]=min(ll[x],ll[y]);
}
else
{
if (onst[y]) ll[x]=min(ll[x],idx[y]);
}
}
if (ll[x]==idx[x])
{
nr++;
while (st[p]!=x)
{
rez[nr].push_back(st[p]);
onst[st[p]]=0;
p--;
}
rez[nr].push_back(st[p]),onst[st[p]]=0,p--;
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,i,j,x,y;
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
a[x].push_back(y);
}
for (i=1;i<=n;i++)
if (!idx[i]) tarjan(i);
g<<nr<<'\n';
for (i=nr;i>=1;i--)
{
for (j=rez[i].size()-1;j>=0;j--)
g<<rez[i][j]<<' ';
g<<"\n";
}
f.close();
g.close();
return 0;
}