Pagini recente » Cod sursa (job #1040811) | Cod sursa (job #2269167) | oji_2012_10 | Cod sursa (job #1017457) | Cod sursa (job #1150240)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100009
using namespace std;
struct vecini
{
vector<int> v;
};
vecini g[nmax],rasp[nmax];
int lowlink[nmax];
int index[nmax],curent=0,nr=0;
stack<int> st;bool stiva[nmax];
void tarjan(int x)
{
curent++;
index[x]=curent;
lowlink[x]=curent;
st.push(x);
stiva[x]=true;
int lung=g[x].v.size(),i,y;
for(i=0;i<lung;++i)
{
y=g[x].v[i];
if(index[y]==0)
{
tarjan(y);
lowlink[x]=min(lowlink[x],lowlink[y]);
}
else
{
if(stiva[y]==true)
lowlink[x]=min(lowlink[x],index[y]);
}
}
if(index[x]==lowlink[x])
{
nr++;
y=st.top();
do
{
y=st.top();
rasp[nr].v.push_back(y);
st.pop();
stiva[y]=false;
}
while(x!=y);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n,m,i,j,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
g[x].v.push_back(y);
}
for(i=1;i<=n;i++)
if(index[i]==0)
{
tarjan(i);
}
printf("%d\n",nr);
for(i=1;i<=nr;i++)
{
for(j=0;j<rasp[i].v.size();++j)
printf("%d ",rasp[i].v[j]);
printf("\n");
}
return 0;
}