Pagini recente » Cod sursa (job #2771037) | Cod sursa (job #388120) | Cod sursa (job #1368952) | Cod sursa (job #2971068) | Cod sursa (job #952962)
Cod sursa(job #952962)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int N,M,x,y,index[100100],lowlink[100100],ind=0,nr=0,s[100100],roots[100100];
vector <int> a[100100],S,rez;
void strongconnect(int k)
{
index[k]=ind;
lowlink[k]=ind;
++ind;
S.push_back(k);
s[k]=1;
int z=a[k].size();
for(int i=0;i<z;++i)
{
if(index[a[k][i]]==-1)
{
strongconnect(a[k][i]);
lowlink[k]=min(lowlink[k],lowlink[a[k][i]]);
}
else if (s[a[k][i]]==1)
{
lowlink[k]=min(lowlink[k],index[a[k][i]]);
}
}
if(lowlink[k]==index[k])
{
roots[k]=1;
++nr;
int w=S.back();
rez.push_back(w);
S.pop_back();
s[w]=0;
while(w!=k)
{
w=S.back();
rez.push_back(w);
S.pop_back();
s[w]=0;
}
}
return;
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
}
for(int i=1;i<=N;++i)
index[i]=-1;
for(int i=1;i<=N;++i)
if(index[i]==-1)
strongconnect(i);
printf("%d\n",nr);
int d=rez.size();
for(int i=0;i<d;++i)
{
printf("%d ",rez[i]);
if(roots[rez[i]]==1)
printf("\n");
}
return 0;
}