Pagini recente » Cod sursa (job #2744771) | Cod sursa (job #832166) | Cod sursa (job #2838170) | Cod sursa (job #427090) | Cod sursa (job #299735)
Cod sursa(job #299735)
#include<stdio.h>
#include<vector>
#include<stack>
#include<bitset>
#include<algorithm>
using namespace std;
#define N 100005
#define pb push_back
int n,m,index1;
bitset<N> inst;
vector<int> a[N],ind,indlow,com;
vector< vector<int> > c;
stack<int> st;
inline void citire()
{
scanf("%d%d",&n,&m);
ind.assign(n+3,0);
indlow.resize(n+3);
int x,y;
for(int i=0; i<m; ++i)
{
scanf("%d%d",&x,&y);
a[x].pb(y);
}
}
void tarjan(int nod)
{
ind[nod]=indlow[nod]=++index1;
st.push(nod);
inst[nod]=1;
for(int i=0,lim=a[nod].size(); i<lim; ++i)
{
int nod1=a[nod][i];
if(!ind[nod1])
{
tarjan(nod1);
indlow[nod]=min(indlow[nod],indlow[nod1]);
}
else
if(inst[nod1])
indlow[nod]=min(indlow[nod],indlow[nod1]);
}
if(ind[nod]==indlow[nod])
{
com.clear();
int nod1;
do
{
nod1=st.top();
st.pop();
inst[nod1]=0;
com.pb(nod1);
}while(nod1!=nod);
c.pb(com);
}
}
inline void rezolva()
{
for(int i=1; i<=n; ++i)
{
if(ind[i])
continue;
tarjan(i);
}
}
inline void scrie()
{
printf("%u\n",c.size());
for(int i=0,lim=c.size(); i<lim; ++i)
{
for(int j=0,lim1=c[i].size(); j<lim1; ++j)
printf("%d ",c[i][j]);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
rezolva();
scrie();
return 0;
}