Pagini recente » Cod sursa (job #440939) | Cod sursa (job #438783) | Cod sursa (job #110986) | Cod sursa (job #2729245) | Cod sursa (job #327035)
Cod sursa(job #327035)
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
#define nmax 200001
using namespace std;
int min(int,int);
vector<int> adj[nmax],con,idx,lowlink,in_stack;
vector<vector<int> > c;
stack<int> s;
int ind;
void tarjan(int n,vector<int>*adj)
{
idx[n]=lowlink[n]=ind;
ind++;
s.push(n);
in_stack[n]=1;
vector<int>::const_iterator it;
for(it=adj[n].begin();it!=adj[n].end();it++)
{
if(idx[*it]==-1)
{
tarjan(*it,adj);
lowlink[n]=min(lowlink[n],lowlink[*it]);
}
else
if(in_stack[*it])
lowlink[n]=min(lowlink[n],lowlink[*it]);
}
if(idx[n]==lowlink[n])
{
con.clear();
int nod;
do
{
con.push_back(nod=s.top());
s.pop();
in_stack[nod]=0;
}
while(nod!=n);
c.push_back(con);
}
}
int main()
{
int n,m,x,y,i,j;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for(;m;m--)
{
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(i=0;i<n;i++)
if(idx[i]==-1)
tarjan(i,adj);
printf("%d\n",c.size());
for(i=0;i<c.size();i++)
{
for(j=0;j<c[i].size();j++)
printf("%d ",c[i][j]+1);
printf("\n");
}
return 0;
}
int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}