Pagini recente » Cod sursa (job #786654) | Cod sursa (job #933464) | Cod sursa (job #348513) | Cod sursa (job #890618) | Cod sursa (job #1922337)
#include <fstream>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,index,m,i,nr,a[101][101],viz[101],pes[101],ll[101];
int sol[101][101],k[101];
stack <int> S;
void tc(int v)
{ viz[v]=index;
ll[v]=index;
index++;
S.push(v);
pes[v]=1;
for(int j=1;j<=n;j++)
{ if(!viz[j] and a[v][j])
{
tc(j);
ll[v]=min(ll[v],ll[j]);
}
else if(pes[j] and a[v][j])
ll[v]=min(ll[v],viz[j]);
}
if(ll[v]==viz[v])
{ nr++;
int w;
do
{ w=S.top();
sol[nr][++k[nr]]=w;
S.pop();
pes[w]=0;
}
while(w!=v);
}
}
void tarjan()
{ index=0;
for(i=1;i<=n;i++)
if(!viz[i]) {tc(i);}
}
int main()
{ f>>n>>m;
for(i=1;i<=m;i++)
{ int u,v;
f>>u>>v;
a[u][v]=1;
}
tarjan();
g<<nr<<'\n';
for (i=1;i<=nr;i++)
{
for (int j=1;j<=k[i];j++)
g<<sol[i][j]<<' ';
g<<'\n';
}
g.close();
return 0;
}