tarjan算法是在dfs生成一颗dfs树的时候按照访问顺序的先后，为每个结点分配一个时间戳，然后再用low[u]表示结点能访问到的最小时间戳
以上的各种应用都是在此拓展而来的。
割点：如果一个图去掉某个点，使得图的连通分支数增加，那么这个点就是割点
某个点是割点，当且仅当这个点的后代没有连回自己祖先的边。即low[v] >= dfn[u] ， v是u的后代
需要注意的是根结点的特判，因为根结点没有祖先，根结点是割点，当且仅当根结点有两个以上的儿子。
问题：重边对该算法有影响吗？没有影响。
需要注意的地方？ 图至少有三个点以上， 否则需要注意一下。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
const int INF = <<;
const int N = + ;
vector<int> g[N];
int dfs_clock,dfn[N],low[N];
bool isCut[N];
void init(int n)
{
dfs_clock = ;
for(int i=; i<=n; ++i)
dfn[i] = low[i] = isCut[i] = ;
}
//重边对割点没有影响，且该算法对有向图同样适用
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfs_clock;
int child = ;
for(int i=; i<g[u].size(); ++i)
{
int v = g[u][i];
if(v==fa) continue;//如果是树枝边的反向访问，则不能用来更新low[u]
child++;
if(dfn[v]==)
tarjan(v,u);
low[u] = min(low[u],low[v]);//用树枝边，或者后向边来跟新low[u]
if(low[v] >= dfn[u])
isCut[u] = true;
}
if(fa==- && child>=) isCut[u] = true;
}
int main()
{
int n,m,i,u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
init(n);
for(i=; i<m; ++i)
{
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
tarjan(,-);
for(i=; i<=n; ++i)
if(isCut[i])
printf("%d ",i);
puts("");
}
return ;
}
割边：如果一个图去掉某条边，使得图的连通分支数增加，那么这条边就是割边（桥）
某条边是割边，当且仅当某个点的后代没有连回自己或者自己祖先的边，即low[v] > dfn[u], 那么边(u,v)是割边
问题：重边对该算法有影响吗？ 有影响。 所以要判断是不是有重边
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
const int INF = <<;
const int N = + ;
vector<int> g[N];
int dfs_clock,dfn[N],low[N],cntCut;
void init(int n)
{
cntCut = dfs_clock = ;
for(int i=; i<=n; ++i)
{
dfn[i] = low[i] = ;
g[i].clear();
}
}
//重边对割边有影响，比如有2--3 ,2--3两条边，那么边2--3就不是割边，因为去掉还是连通的，所以要判断一下
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfs_clock;
bool flag = false;
for(int i=; i<g[u].size(); ++i)
{
int v = g[u][i];
if(v==fa && !flag)//在这里判断有没有重边
{
flag = true;
continue;
}
if(dfn[v]==)
tarjan(v,u);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u])//这里统计的是割边的数量，如果要记录割边，那么就标记边，或者把边入栈
cntCut++;
}
}
int main()
{
int n,m,i,u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
init(n);
for(i=; i<m; ++i)
{
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
tarjan(,-);
printf("%d\n",cntCut);
}
return ;
}
点-双连通分量：如果任意两点存在两条点不重复的路径，那么就说这个图是点-双连通的。点-双连通的极大子图称为双连通分量
双连通分量之间的分界点是割点。而且双连通分量不可能分布在树根结点两端。所以我们将边入栈，当遇到割点时，就将边出栈，直到有边等于当前边。就跳出
问题：重边对该算法有影响吗？ 没有影响
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
const int INF = <<;
const int N = + ;
struct Edge
{
int u,v;
Edge(){};
Edge(int u, int v)
{
this->u = u;
this->v = v;
}
};
vector<int> g[N],bcc[N];
int bccno[N],dfn[N],low[N],dfs_clock,cnt;
stack<Edge> st;
void init(int n)
{
cnt = dfs_clock = ;
for(int i=; i<=n; ++i)
{
bccno[i] = low[i] = dfn[i] = ;
bcc[i].clear();
g[i].clear();
}
}
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfs_clock;
for(int i=; i<g[u].size(); ++i)
{
int v = g[u][i];
if(dfn[v]==)
{
st.push(Edge(u,v));
tarjan(v,u);
low[u] = min(low[u],low[v]);
if(low[v] >= dfn[u])//如果这个点是割点，那么先前入栈的一些边是属于一个双连通分量的
{
Edge x;
cnt++;
for(;;)
{
x = st.top();
st.pop();
if(bccno[x.u] != cnt)
{
bccno[x.u] = cnt;
bcc[cnt].push_back(x.u);
}
if(bccno[x.v] != cnt)
{
bccno[x.v] = cnt;
bcc[cnt].push_back(x.v);
}
if(x.u==u && x.v==v)
break;
}
}
}
else if(v!=fa && dfn[v] < dfn[u])
{
st.push(Edge(u,v));
low[u] = min(low[u],dfn[v]);
} }
}
int main()
{
int n,m,i,u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
init(n);
for(i=; i<m; ++i)
{
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
tarjan(,-);
for(i=; i<=cnt; ++i)
{
printf("bcc %d has vertex:",i);
while(!bcc[i].empty())
{
printf("%d ",bcc[i].back());
bcc[i].pop_back();
}
puts("");
}
}
return ;
}
边-双连通分量：如果任意两点存在两条边不重复的路径，那么就说这个图是边-双连通的，边-双连通的极大子图成为边双连通分量。
边双连通分量的分界点是割边。双连通分量可以分布在根结点的两端。所以不能在for(int i=0; i<g[u].size(); ++i) 这个循环里面判断割边，而要在外面递归返回时判断
问题：重边对该算法有影响吗？有影响，就好像影响割边算法一样
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
const int INF = <<;
const int N = + ;
vector<int> g[N];
stack<int> st;
int dfn[N],low[N],dfs_clock,bccno[N],cnt;
void init(int n)
{
cnt = dfs_clock = ;
for(int i=; i<n; ++i)
{
dfn[i] = low[i] = ;
bccno[i] = ;
g[i].clear();
}
} void tarjan(int u, int fa)//边双连通分量可能分布在某子树树根的两个分支上
{
low[u] = dfn[u] = ++dfs_clock;
st.push(u);
bool flag = ;
for(int i=; i<g[u].size(); ++i)
{
int v = g[u][i];
if(v==fa && !flag) //重边对边连通分量的判断有影响，所以要判断一下
{
flag = true;
continue;
}
if(dfn[v]==)
tarjan(v,u);
low[u] = min(low[u],low[v]);
}
if(dfn[u]==low[u])//说明这个点的所有后代都没有连回自己祖先的边，
{
cnt++;
for(;;)
{
int x = st.top();
st.pop();
bccno[x] = cnt;
if(x==u)
break;
}
}
}
int main()
{
int n,m,i,u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
init(n);
for(i=; i<m; ++i)
{
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
tarjan(,-);
for(i=; i<=n; ++i)
printf("vexter %d belong to bcc %d\n",i,bccno[i]);
}
return ;
}
问添加最少多少条边，使得整个图边-双连通， 首先求出边-双连通分量，然后缩点，最后变成一棵树，那么要加的边 就是（叶子结点+1)/2
强连通分量：如果有向图的任意两点可以，那么就说这个图是强连通的，一个图的极大子图是强连通的，那么就说这个子图是强连通分量
对于一个scc，我们要判断哪个点是该scc最先被发现的点，然后将后来发现的点出栈，知道遇到这个点。 那么出栈的点都属于一个强连通分量
问题：重边对该算法有影响吗？没有影响
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
const int INF = <<;
const int N = + ;
vector<int> g[N];
stack<int> st;
int cnt,dfs_clock,dfn[N],low[N],sccno[N];
void init(int n)
{
cnt = dfs_clock = ;
for(int i=; i<=n; ++i)
{
dfn[i] = low[i] = sccno[i] = ;
g[i].clear();
}
} void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfs_clock;
st.push(u);
for(int i=; i<g[u].size(); ++i)
{
int v = g[u][i];
if(dfn[v]==)
{
tarjan(v,u);
low[u] = min(low[u],low[v]);
}
else if(sccno[v]==)//因为有向图存在横插边，不能用横插边来更新low[u]
{
low[u] = min(low[u],low[v]);
}
}
//同样，因为强连通分量可以分布在根结点的两个分支上，所以在递归返回的时候调用
if(low[u] == dfn[u])
{
cnt++;
for(;;)
{
int x = st.top();
st.pop();
sccno[x] = cnt;
if(x==u)
break;
}
}
}
int main()
{
int n,m,i,u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
init(n);
for(i=; i<m; ++i)
{
scanf("%d%d",&u,&v);
g[u].push_back(v);
}
tarjan(,-);
for(i=; i<=n; ++i)
printf("vertex %d belong to scc %d\n",i,sccno[i]);
}
return ;
}