Pagini recente » Cod sursa (job #1548415) | Cod sursa (job #697158) | Cod sursa (job #2256133) | Cod sursa (job #2500519) | Cod sursa (job #484819)
Cod sursa(job #484819)
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_V 100000
vector<int> L[MAX_V];
int V,dfsPos,dfsNum[MAX_V],lowlink[MAX_V],num_scc;
bool in_stack[MAX_V];
vector<int> C[MAX_V];
stack<int> S;
void tarjan(int v){
dfsNum[v] = lowlink[v] = dfsPos;
++dfsPos;
S.push(v); in_stack[v] = true;
for(int i = L[v].size()-1;i>=0;--i){
int w = L[v][i];
if(dfsNum[w]==-1){
tarjan(w);
lowlink[v] = min(lowlink[v],lowlink[w]);
}else if(in_stack[w]) lowlink[v] = min(lowlink[v], lowlink[w]);
}
if(dfsNum[v]==lowlink[v]){
vector<int> com;
int aux;
do{
aux = S.top(); S.pop();
com.push_back(aux);
in_stack[aux] = false;
}while(aux!=v);
C[num_scc] = com;
++num_scc;
}
}
void build_scc(){
memset(dfsNum,-1,sizeof(dfsNum));
memset(in_stack,false,sizeof(in_stack));
dfsPos = num_scc = 0;
for(int i = 0;i<V;++i)
if(dfsNum[i]==-1)
tarjan(i);
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int M,u,v;
scanf("%d %d",&V,&M);
while(M--){
scanf("%d %d",&u,&v);
L[u-1].push_back(v-1);
}
build_scc();
printf("%d\n",num_scc);
for(int i = 0;i<num_scc;++i){
for(int j = C[i].size()-1;j>=0;--j)
printf("%d ",1+C[i][j]);
printf("\n");
}
return 0;
}