DFN[u]：u被搜索的次序编号
LOW[u]：u的子树中最小编号
有向图：当DFN(u)=LOW(u)时，以u为根的树上所有点是一个强连通分量
无向图：当LOW[v]>DNF[u]时(u,v)为桥
Tarjan缩点代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
// <Tarjan缩点.cpp> - 10/26/15 14:12:33 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <stack> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } vector <int> b[10001]; int dfn[10001],low[10001]; int edge[200001]; bool usd[10001]; int n,m,ans,k; stack <int> st; void tarjan(int x){ dfn[x]=low[x]=++k; st.push(x);usd[x]=1; for(int i=0;i<b[x].size();i++){ int next=b[x][i]; if(!dfn[next]){ tarjan(next); low[x]=min(low[x],low[next]); }else if(usd[next])low[x]=min(low[x],dfn[next]); } int next; if(low[x]==dfn[x]){ ans++; do{ next=st.top();st.pop(); usd[next]=0; }while(next!=x); } } int main(){ n=getint();m=getint(); for(int i=0;i<m;i++){ int u=getint()-1,v=getint()-1; b[u].push_back(v); } for(int i=0;i<n;i++)if(!dfn[i])tarjan(i); cout<<ans<<endl; return 0; } |
Tarjan求桥代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// <Tarjan求桥.cpp> - 10/26/15 14:12:33 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } vector <int> b[10001]; int dfn[10001],low[10001]; int edge[200001]; int n,m,k,ans; void tarjan(int x,int f){ dfn[x]=low[x]=++k; for(int i=0;i<b[x].size();i++){ int next=edge[b[x][i]]; if(!dfn[next]){ tarjan(next,b[x][i]); low[x]=min(low[x],low[next]); if(low[next]>dfn[x])ans++; }else if(b[x][i]>>1!=f>>1)low[x]=min(low[x],dfn[next]); } } int main(){ n=getint();m=getint(); for(int i=0;i<m;i++){ int u=getint()-1,v=getint()-1; edge[i*2]=v; edge[i*2+1]=u; b[u].push_back(i*2); b[v].push_back(i*2+1); } for(int i=0;i<n;i++)if(!dfn[i])tarjan(i,-1); cout<<ans<<endl; return 0; } |