Pagini recente » Cod sursa (job #1930218) | Cod sursa (job #2130385) | Cod sursa (job #1581524) | Cod sursa (job #1416564) | Cod sursa (job #760418)
Cod sursa(job #760418)
#include <stdio.h>
#include <vector>
#include <stack>
#define NMax 100010
using namespace std;
const char IN[]="ctc.in",OUT[]="ctc.out";
int N,M,index;
int T[NMax],t[NMax];
bool b[NMax] , inSt[NMax];
vector<int> ad[NMax] ;
stack<int> st;
vector<vector<int> > Sol;
void tarjan(int x)
{
b[x]=true;
inSt[x]=true;st.push(x);
t[x]=T[x]=++index;
for (int i=0;i<(int)ad[x].size();++i) if (!b[ad[x][i]])
{
tarjan(ad[x][i]);
T[x]=min(T[x],T[ad[x][i]]);
}
else if (inSt[ad[x][i]]) T[x]=min(T[x],T[ad[x][i]]);
if (T[x]==t[x])
{
vector<int> vec;
while (st.top()!=x)
{
vec.push_back(st.top());
inSt[st.top()]=false;
st.pop();
}
vec.push_back(st.top());
inSt[st.top()]=false;
st.pop();
Sol.push_back(vec);
}
}
int main()
{
int x,y;
freopen(IN,"r",stdin);
scanf("%d%d",&N,&M);
while (M--)
{
scanf("%d%d",&x,&y);
ad[x].push_back(y);
}
fclose(stdin);
for (int i=1;i<=N;++i) if (!b[i])
tarjan(i);
freopen(OUT,"w",stdout);
printf("%d\n",Sol.size());
for (int i=0;i<(int)Sol.size();++i,printf("\n"))
for (int j=0;j<(int)Sol[i].size();++j)
printf("%d ",Sol[i][j]);
fclose(stdout);
return 0;
}