Pagini recente » Cod sursa (job #1506428) | Cod sursa (job #2804074) | Cod sursa (job #2838421) | Cod sursa (job #3220337) | Cod sursa (job #662028)
Cod sursa(job #662028)
#include<cstdio>
#include<vector>
#include<bitset>
#define V 100001
using namespace std;
vector<vector<int> > CTC;
vector<int> v[V],S,P,ctc;
bitset<V> U;
int n,m,x,y,Nr[V];
void DF(int);
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(;m;m--){scanf("%d%d",&x,&y);v[x].push_back(y);}
for(int i=1;i<=n;i++)if(!Nr[i])DF(i);
n=CTC.size();printf("%d\n",n);
for(n--;n>=0;n--)
{
for(;CTC[n].size();){printf("%d ",CTC[n].back());CTC[n].pop_back();}
printf("\n");
CTC.pop_back();
}
return 0;
}
void DF(int nod)
{
Nr[nod]=++m;S.push_back(nod);P.push_back(nod);
for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
{
if(!Nr[*it]){DF(*it);continue;}
if(U[*it])continue;
while(Nr[P.back()]>Nr[*it])P.pop_back();
}
if(P.back()!=nod)return;
ctc.resize(0);
for(x=-1;x-nod;){x=S.back();U[x]=1;ctc.push_back(x);S.pop_back();}
CTC.push_back(ctc);
P.pop_back();
}