Pagini recente » Cod sursa (job #422661) | Cod sursa (job #2066015) | Cod sursa (job #2598596) | Cod sursa (job #1590857) | Cod sursa (job #793515)
Cod sursa(job #793515)
#include <stdio.h>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
stack<int> stac;
vector< vector<int> >G(100005);
int n,m;
bitset<100005> viz;
bitset<100005> inStack;
vector< vector<int> > scc;
int nr=1,num[100005],low[100005];
int min(int a,int b){return a<b?a:b;}
void dfs(int u){
viz[u]=1;stac.push(u);inStack[u]=true;
low[u]=num[u]=nr++;
int v;
for(int i=0;i<G[u].size();i++){
v=G[u][i];
if(!viz[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else{
if(inStack[v])
low[u]=min(low[u],num[v]);
}
}
if(low[u]==num[u]){
vector<int> newV;
while(true){
v=stac.top();stac.pop();inStack[v]=false;
newV.push_back(v);
if(v==u) break;
}
scc.push_back(newV);
}
}
int main(){
int x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d",&n);scanf("%d",&m);
for(int i=0;i<m;i++){scanf("%d",&x);scanf("%d",&y);G[x].push_back(y);}
viz.reset();
for(int i=1;i<=n;i++) if(!viz[i]) dfs(i);
printf("%d\n",scc.size());
for(int i=0;i<scc.size();i++){
for(int j=0;j<scc[i].size();j++)
printf("%d ",scc[i][j]);
printf("\n");
}
return 0;
}