tarjan强连通分量
wenge
2020-02-12 22:43:58
```cpp
vector<int> f[100005];
int t=0,dfn[100005],low[100005],instack[100005],fa[100005];
stack<int> st;
void tarjan(int x){
t++;
dfn[x]=low[x]=t;
st.push(x);
instack[x]=1;
for(int i=0;i<f[x].size();i++){
int y=f[x][i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(instack[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
while(1){
int p=st.top();
instack[p]=0;
st.pop();
fa[p]=x;
if(p==x)break;
}
}
}