Pagini recente » Cod sursa (job #1512611) | Cod sursa (job #1676466) | Cod sursa (job #155860) | Cod sursa (job #2171635) | Cod sursa (job #932619)
Cod sursa(job #932619)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100100
#define minim(a,b) ((a<b)?(a):(b))
int N,M,Nctc,index;
int Idx[NMAX];
int Llink[NMAX];
bool inStack[NMAX];
vector < int > G[NMAX],CTC[NMAX];
stack < int > Stack;
void Read() {
freopen("ctc.in","r",stdin);
int x,y;
scanf("%d%d",&N,&M);
while(M--) {
scanf("%d%d",&x,&y);
G[x].push_back(y);
}
}
void Tarjan(int nod) {
Idx[nod]=Llink[nod]=index++;
Stack.push(nod);
inStack[nod]=true;
for(unsigned j=0;j<G[nod].size();++j) {
int vecin=G[nod][j];
if(!Idx[vecin]) {
Tarjan(vecin);
Llink[nod]=minim(Llink[vecin],Llink[nod]);
}
else
if(inStack[vecin])
Llink[nod]=minim(Llink[vecin],Llink[nod]);
}
if(Idx[nod]==Llink[nod]) {
Nctc++;
int STop;
do {
STop = Stack.top();
CTC[Nctc].push_back(STop);
inStack[STop]=false;
Stack.pop();
}while(STop!=nod);
}
}
void TSFH(){
for(int i=1;i<=N;i++)
if(!Idx[i])
Tarjan(i);
}
void Print() {
freopen("ctc.out","w",stdout);
printf("%d\n",Nctc);
for(int i=1;i<=Nctc;++i) {
for(unsigned j=0;j<CTC[i].size();++j)
printf("%d ",CTC[i][j]);
printf("\n");
}
}
int main(){
Read();
TSFH();
Print();
return 0;
}