Pagini recente » Cod sursa (job #2103435) | Cod sursa (job #1362925) | Cod sursa (job #57857) | Cod sursa (job #2419282) | Cod sursa (job #899525)
Cod sursa(job #899525)
#include <cstdio>
#include <vector>
#include <stack>
#define MAX 1000005
using namespace std;
int n,m,indecs;
vector <vector <int> > C;
vector <int> adj[MAX],con,in_stack,index,lowlink;
stack <int> S;
int minim(int a, int b)
{
if(a<b)
return a;
return b;
}
void tarjan(int a)
{
index[a]=indecs;
lowlink[a]=indecs;
indecs++;
S.push(a);in_stack[a]=1;
int b=adj[a].size();
for(int k=0;k<b;k++)
if(index[adj[a][k]]==-1)
{
tarjan(adj[a][k]);
lowlink[a]=minim(lowlink[a],lowlink[adj[a][k]]);
}
else
if(in_stack[adj[a][k]])
lowlink[a]=minim(lowlink[a],lowlink[adj[a][k]]);
if(index[a]==lowlink[a])
{
con.clear();
int nod;
do
{
nod=S.top();
con.push_back(nod);
S.pop();
}while(nod!=a);
C.push_back(con);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
int x,y;
for(int k=1;k<=m;k++)
{
scanf("%d %d",&x,&y);
adj[x-1].push_back(y-1);
}
index.resize(n);in_stack.resize(n);lowlink.resize(n);
in_stack.assign(n,0);index.assign(n,-1);
for(int k=0;k<=n-1;k++)
if(index[k]==-1)
tarjan(k);
printf("%d\n",x=C.size());
for(int k=0;k<x;k++)
{
y=C[k].size();
for(int j=0;j<y;j++)
printf("%d ",C[k][j]+1);
printf("\n");
}
}