Pagini recente » Cod sursa (job #2153313) | Statisticile problemei Cinema | Cod sursa (job #1337883) | Monitorul de evaluare | Cod sursa (job #1963790)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n,m,i,j,x,y,t,k,nr,d[100005],low[100005],st[100005];
bool viz[100005];
vector <int> v[100005],sol[100005];
void dfs(int nod)
{
t++;
d[nod]=low[nod]=t;
st[++k]=nod;
viz[nod]=1;
for (int i=0; i<v[nod].size(); i++)
if (d[v[nod][i]]==0)
{
dfs(v[nod][i]);
low[nod]=min(low[nod],low[v[nod][i]]);
}
else
if(viz[v[nod][i]]==1)
low[nod]=min(low[nod],d[v[nod][i]]);
if(low[nod]==d[nod]){
nr++;
do{
x=st[k--];
viz[x]=0;
sol[nr].push_back(x);
}while(x!=nod&&k>0);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1; i<=m; i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
}
for(i=1;i<=n;i++)
if(d[i]==0)
dfs(i);
printf("%d\n",nr);
for (i=1; i<=nr; i++)
{
for (j=0; j<sol[i].size(); j++)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}