Pagini recente » Cod sursa (job #2265391) | Cod sursa (job #1427190) | Cod sursa (job #21962) | Cod sursa (job #2258391) | Cod sursa (job #899575)
Cod sursa(job #899575)
#include <cstdio>
#include <vector>
#include <stack>
#define MAX 100005
using namespace std;
vector <int> adj[MAX],idx,lowlink,in_stack,con;
vector <vector <int> > C;
stack <int> S;
int n, m,indecs;
int minim (int a, int b)
{
if(a<b)
return a;
return b;
}
void tarjan(int a)
{
idx[a]=indecs;
lowlink[a]=indecs;
S.push(a);
in_stack[a]=1;
indecs++;
//
for(int k=0;k<adj[a].size();k++)
if(idx[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(idx[a]==lowlink[a])
{
con.clear();
int node;
do
{
node=S.top();
con.push_back(node);
S.pop();
in_stack[node]=0;
}while(node!=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);
}
idx.resize(n), lowlink.resize(n), in_stack.resize(n);
idx.assign(n, -1), in_stack.assign(n, 0);
for(int k=0;k<n;k++)
if(idx[k]==-1)
tarjan(k);
printf("%d\n",C.size());
for(int k=0;k<=C.size()-1;k++)
{
for(int j=0;j<=C[k].size()-1;j++)
printf("%d ",C[k][j]+1);
printf("\n");
}
return 0;
}