Pagini recente » Cod sursa (job #675909) | Cod sursa (job #707626) | Cod sursa (job #1623859) | Cod sursa (job #2110578) | Cod sursa (job #831028)
Cod sursa(job #831028)
#include<cstdio>
#include<vector>
#include<stack>
#define MAX 100001
using namespace std;
struct nod{
int index,lowlink;
}v[MAX];
vector <int> graf[MAX];
vector < vector <int> > ctc;
stack <int> S;
bool viz[MAX],inS[MAX];
int n,m,ind;
void strongconnect(int x){
int i,vf;
ind++;viz[x]=1;
v[x].index=ind;
v[x].lowlink=ind;
S.push(x);inS[x]=1;
for(i=0;i<(int)graf[x].size();i++){
vf=graf[x][i];
if(!viz[vf]){
strongconnect(vf);
v[x].lowlink=min(v[x].lowlink,v[vf].lowlink);
}
else if(inS[vf])
v[x].lowlink=min(v[x].lowlink,v[vf].lowlink);
}
if(v[x].lowlink==v[x].index){
vector <int> vec;
while(S.top()!=x){
vec.push_back(S.top());
inS[S.top()]=0;
S.pop();
}
vec.push_back(S.top());
inS[S.top()]=0;
S.pop();
ctc.push_back(vec);
}
}
void Tarjan(){
int i;
for(i=1;i<=n;i++)
if(!viz[i])
strongconnect(i);
}
int main(){
int i,j,x,y;
freopen("ctc.in","r",stdin);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
graf[x].push_back(y);
}
fclose(stdin);
Tarjan();
freopen("ctc.out","w",stdout);
printf("%d\n",ctc.size());
for(i=0;i<(int)ctc.size();i++){
for(j=0;j<(int)ctc[i].size();j++)
printf("%d ",ctc[i][j]);
printf("\n");
}
fclose(stdout);
return 0;
}