Pagini recente » Cod sursa (job #272755) | Cod sursa (job #2552112) | Cod sursa (job #1860837) | Cod sursa (job #329592) | Cod sursa (job #976121)
Cod sursa(job #976121)
#include<stdio.h>
#include<stack>
#include<vector>
#define pb push_back
#define maxn 100005
using namespace std;
int n,m,nr,pas;
int low[maxn],ind[maxn],v[maxn];
vector <int> l[maxn],sol[maxn];
stack <int> s;
void cit()
{
int i;
int x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
l[x].pb(y);
}
}
void add(int k)
{
int i;
nr++;
while(s.top()!=k)
{
sol[nr].pb(s.top());
v[s.top()]=0;
s.pop();
}
sol[nr].pb(k);
v[s.top()]=0;
s.pop();
}
void df(int k)
{
pas++;
s.push(k); v[k]=1;
low[k]=ind[k]=pas;
for(unsigned int i=0;i<l[k].size();i++)
if(ind[l[k][i]]==0)
{
df(l[k][i]);
low[k]=min(low[k],low[l[k][i]]);
}
else
if(v[l[k][i]])
low[k]=min(low[k],ind[l[k][i]]);
if(low[k]==ind[k])
add(k);
}
void afis()
{
int k,i;
printf("%d\n",nr);
for(k=1;k<=nr;k++)
{
for(unsigned int i=0;i<sol[k].size();i++)
printf("%d ",sol[k][i]);
printf("\n");
}
}
int main()
{
int aux;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
cit();
for(int i=1;i<=n;i++)
if(ind[i]==0)
df(i);
afis();
fclose(stdin);
fclose(stdout);
return 0;
}