Pagini recente » Cod sursa (job #2467318) | Cod sursa (job #2358136) | Cod sursa (job #2344275) | Cod sursa (job #1729812) | Cod sursa (job #1874878)
//componente tari conexe cu tarjan ;)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int i,n,j,m,x,y,nr,k,vp[100010],vm[100010];
vector<int> af[100010],l[100010],*it,sti;
bool viz[100010],vizsti[100010];
void tarjan(int x)
{
viz[x]=1;
sti.push_back(x);
vizsti[x]=1;
for(int i=0;i<l[x].size();++i)
{
if(viz[l[x][i]]==0)
{
++k;
vp[l[x][i]]=k;
vm[l[x][i]]=k;
tarjan(l[x][i]);
vm[x]=min(vm[x],vm[l[x][i]]);
}
else
{
if(vizsti[l[x][i]])
vm[x]=min(vm[x],vm[l[x][i]]);
}
}
if(vm[x]==vp[x])
{
++nr;
while(sti.back()!=x)
{
af[nr].push_back(sti.back());
vizsti[sti.back()]=0;
sti.pop_back();
}
af[nr].push_back(x);
vizsti[x]=0;
sti.pop_back();
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;++i)
{
fin>>x>>y;
l[x].push_back(y);
}
for(i=1;i<=n;++i)
{
if(viz[i]==0)
tarjan(i);
}
fout<<nr<<"\n";
for(i=1;i<=nr;++i)
{
for(j=0;j<af[i].size();++j)
fout<<af[i][j]<<" ";
fout<<"\n";
}
return 0;
}