Pagini recente » Cod sursa (job #3037977) | Profil DranaXum | tabletennis | Cod sursa (job #687414) | Cod sursa (job #2295587)
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<string>
using namespace std;
#define MAXN 100000
#define MAXM 200000
int M,N;
vector<int> L[MAXN+1];
bool viz[MAXN];
typedef struct nod{
int index;
int low;
bool instack;
}nod;
nod V[MAXN+1];
int S[MAXN];
int stack;
int index=1;
int nbcomp;
vector<int> C[MAXN];
void componente(int nod){
viz[nod]=true;
V[nod].index = index;
V[nod].low = index;
V[nod].instack = true;
index++;
S[stack]=nod;
stack++;
vector<int>::iterator it;
int vecin;
for(it=L[nod].begin();it!=L[nod].end();it++){
vecin=*it;
if(!viz[vecin]){
componente(vecin);
if(V[nod].low > V[vecin].low)
V[nod].low = V[vecin].low;
}
else{
if(V[vecin].instack){
if(V[nod].low > V[vecin].index)
V[nod].low = V[vecin].index;
}
}
}
if (V[nod].low == V[nod].index){
// start a new strongly connected component
while(S[stack-1]!=nod){
C[nbcomp].push_back(S[stack-1]);
V[S[stack-1]].instack=false;
stack--;
}
C[nbcomp].push_back(S[stack-1]);
V[S[stack-1]].instack=false;
stack--;
nbcomp++;
}
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d",&N,&M);
int x,y;
for(int i=0;i<M;i++){
scanf("%d %d",&x,&y);
L[x].push_back(y);
}
for(int i=1;i<=N;i++){
if(!viz[i])
componente(i);
}
printf("%d\n",nbcomp);
vector<int>::iterator it;
for(int i=0;i<nbcomp;i++){
for(it=C[i].begin();it!=C[i].end();it++){
printf("%d ",*it);
}
printf("\n");
}
return 0;
}