Pagini recente » Cod sursa (job #1614603) | Cod sursa (job #844998) | Cod sursa (job #1419334) | Cod sursa (job #2233282) | Cod sursa (job #1971809)
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#define nmax 100010
using namespace std;
int idx[nmax],lowlink[nmax],ins[nmax],index;
int n,m1;
vector<int> m[nmax],ctc;
stack<int> s;
vector< vector<int> > sol;
void tarjan(int nod)
{
index++;
int crt;
idx[nod]=index; lowlink[nod]=index;
s.push(nod); ins[nod]=1;
for(vector<int>::iterator it=m[nod].begin();it!=m[nod].end();it++)
if(!idx[*it])
{
tarjan(*it);
lowlink[nod]=min( lowlink[nod],lowlink[*it]);
} else if(ins[*it]) lowlink[nod]=min(lowlink[nod],lowlink[*it]);
if(lowlink[nod]==idx[nod])
{
ctc.clear();
do
{
crt=s.top(); s.pop();
ctc.push_back(crt); ins[crt]=0;
} while(crt!=nod);
sol.push_back(ctc);
}
}
int main()
{
int n1,n2,i,j;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m1);
for(;m1;m1--)
{
scanf("%d%d",&n1,&n2);
m[n1].push_back(n2);
}
for(i=1;i<=n;i++)
if(!idx[i]) tarjan(i);
printf("%d\n",sol.size());
for(i=0;i<sol.size();i++)
{
for(j=0;j<sol[i].size();j++) printf("%d ",sol[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}