Pagini recente » Cod sursa (job #1715187) | Cod sursa (job #686603) | Cod sursa (job #1365461) | Cod sursa (job #2080227) | Cod sursa (job #304102)
Cod sursa(job #304102)
#include <iostream>
#include <algorithm>
#include <vector>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define PB push_back
#define MAX 100010
using namespace std;
struct ceva{ int index,lowlink;} v[MAX];
vector < int > S;
int index=0;
int N,M;
char def[MAX],inS[MAX];
vector < vector < int > > Comp;
vector < int > csol;
vector < int > vecini[MAX];
void tarjan(int nod){
def[nod]=1;
v[nod].index=index;
v[nod].lowlink=index;
++index;
S.PB(nod);
inS[nod]++;
for (int i=1;i<=vecini[nod].size();++i){
if (def[vecini[nod][i-1]]==0 || inS[vecini[nod][i-1]]){
if (def[vecini[nod][i-1]]==0) tarjan(vecini[nod][i-1]);
v[nod].lowlink=min(v[nod].lowlink,v[vecini[nod][i-1]].lowlink);
}
}
if ( v[nod].lowlink==v[nod].index){
int ok=1;
csol.clear();
while(ok){
int element=S[S.size()-1];
inS[element]--;
S.pop_back();
if (element==nod){ok=0;}
csol.PB(element);
}
Comp.PB(csol);
}
}
int main(void){
freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);
scanf("%d%d",&N,&M);
memset(def,0,sizeof(def));
memset(inS,0,sizeof(inS));
int x,y;
for (int i=1;i<=M;++i){
scanf("%d%d",&x,&y);
vecini[x].PB(y);
}
fclose(stdin);
index=0;
for (int i=1;i<=N;++i) if (def[i]==0) tarjan(i);
printf("%d\n",Comp.size());
for (int i=0;i<Comp.size();++i){
for (int j=0;j < (Comp[i].size()-1);++j) printf("%d ",Comp[i][j]);
printf("%d\n",Comp[i][Comp[i].size()-1]);
}
fclose(stdout);
return 0;
}