Pagini recente » Cod sursa (job #76263) | Cod sursa (job #2723219) | Cod sursa (job #1522279) | Cod sursa (job #291624) | Cod sursa (job #904337)
Cod sursa(job #904337)
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define NMax 100010
using namespace std;
const char IN[]="ctc.in",OUT[]="ctc.out";
int N,M;
int T[NMax],idx[NMax];
bool in_stack[NMax];
vector<int> ad[NMax];
stack<int> st;
vector<vector<int> > Sol;
void tarjan(int x,int lv=0){
int i;
static int index;
T[x]=idx[x]=++index;
st.push(x);
in_stack[x]=true;
for (i=0;i<(int)ad[x].size();++i) if (!idx[ad[x][i]])
tarjan(ad[x][i]),
T[x]=min(T[x],T[ad[x][i]]);
else if (in_stack[ad[x][i]])
T[x]=min(T[x],T[ad[x][i]]);
if (idx[x]==T[x]){
vector<int> vec;
for (i=-1;i!=x;){
i=st.top();st.pop();
vec.push_back(i);
in_stack[i]=false;
}
Sol.push_back(vec);
}
}
int main()
{
int i,j,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);
tarjan(1);
freopen(OUT,"w",stdout);
printf("%d\n",Sol.size());
for (i=0;i<(int)Sol.size();++i,printf("\n"))
{
sort(Sol[i].begin(),Sol[i].end());
for (j=0;j<(int)Sol[i].size();++j)
printf("%d ",Sol[i][j]);
}
fclose(stdout);
return 0;
}