先说一下割点跟割边吧。
割桥就是如果一个连通图里删除这条边之后，这个图会变成两个连通图，那么这条边就称之为割桥。
这是割桥的代码，里面呆着lca求法。
割点和割桥的就是用一个时间戳和回到祖先确定。
用dfs的时间戳可以看出。
割点为low[v] >= dfn[u]
割边为low[v] > dfn[u]。
但是要注意的是割点的条件对于搜索树的根节点是要特殊处理的，当根节点的孩子大于1的时候就一定是割点。
void tarjan(int u,int pre)
{
int v,i,j;
dfn[u] = low[u] = ++dfsclock;
loop(,i,g[u].size())
{
v = g[u][i];
if(!dfn[v])//保证是树枝边
{
tarjan(v,u);
father[v] = u;//v的父亲是u
low[u] = min(low[v],low[u]);
if(low[v] > dfn[u])//加入v回到的祖先小于u那么u,v一定是桥。
cut++;
else
merge(u,v);
}
else if(v != pre)//保证不是直向自己父亲的遍
low[u] = min(low[u],dfn[v]);
}
}
void lca(int u,int v)//最后的u和v是同一个最近祖先
{ while(u != v)
{
while(dfn[u] >= dfn[v] && u != v)//v遍历的比较早
{
if(merge(u,father[u]))//如果u的父亲和u不是在一个环里也就是不在缩点之后的同一个点，那么就是缩点之后的桥
cut--;
u = father[u];
}
while(dfn[v] >= dfn[u] && u != v)
{
if(merge(v,father[v]))
cut--;
v = father[v];
}
}
}
割点就是如果一个连通图删除了某个点和相关的边之后那么，这个图就是变成两个连通图， 这个点叫做割点。
这是割点代码
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stack>
#define loop(s,i,n) for(i = s;i < n;i++)
#define cl(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = ;
vector<int>g[maxn];
int is_cut[maxn],dfn[maxn],low[maxn]; int dfsclock;
int cut;
void init(int n)
{
int i;
for(i = ;i <= n;i++)
g[i].clear();
dfsclock = ;
cl(is_cut,);
cl(low,);
cl(dfn,);
cut = ;
return ;
}
void tarjan(int u,int pre)
{
dfn[u] = low[u] = ++dfsclock;
int i;
int child = ;
for(i = ;i < g[u].size();i++)
{
int v;
v = g[u][i]; if(!dfn[v])//保证是没访问过的树枝边。
{
child++;//这里要加一个孩子数，为的是后面对树根的判断。
tarjan(v,u);
if(low[v] < low[u])
low[u] = low[v];
if(low[v] >= dfn[u])//注意区别。割点与割桥代码差的很少，就这么一点。割点的自己点是可以回到自身的，但是割边不行假如回到了，那么说明是环就一定不是桥~
is_cut[u] = ;
}
else if(v != pre)
low[u] = min(dfn[v],low[u]);
}
if(pre < && child == )//树根的判断。
is_cut[u] = ; return ;
} int main()
{
int u,v,n;
while(scanf("%d",&n)&&n)
{
init(n);//我觉得我这个人活在世上就是为了考验我容忍傻逼的限度。老忘初始化~ read();//就是见图过程，不谢了。
tarjan(,-);//如果不是一个连通图，那么就for一下对每一个!dfn[i]做一次。
int i;
for(i = ;i <= n;i++)
{
if(is_cut[i])
cut++;
}
cout<<cut<<endl;
}
return ;
}
以上是无向图的代码，有向图的自己改一下吧~
这是对于有向图的强连通分量，不多讲。想详细了解一下的话可以看这个：https://www.byvoid.com/blog/scc-tarjan
贴下自己的代码，注意对重边情况要另外写哦~
这是由重边情况的。
const int maxn = ;
bool vis[];
struct edge
{
int v,next;
edge()
{
next = -;
}
}edges[maxn*-];
struct ed
{
int u,v;
}e[maxn*-];
int dfn[],low[],belong[];
bool inst[];
int g[maxn];
vector<int>ng[maxn]; stack<int>st;
int bcnt,cnt,time; void init(int n)
{
int i;
for(i =;i <= n;i++)
g[i] = -;
time = ;bcnt = cnt = ;
return ;
}
void addedge(int u,int v,int val)
{
struct edge o;
edges[cnt].v = v;
edges[cnt].next = g[u];
g[u] = cnt;
cnt++; return ;
}
void tarjan(int i)
{
int j;
dfn[i] = low[i] = ++time;
inst[i] = ;
st.push(i); for(j = g[i];j != -;j = edges[j].next)
{
if(vis[j]) continue;
vis[j] = vis[j^] = ;
int v;
v = edges[j].v;
if(!dfn[v])
{
tarjan(v);
low[i] = min(low[i],low[v]);
}
else if(inst[v])
low[i] = min(low[i],dfn[v]);
}
int k;
if(dfn[i] == low[i])
{ bcnt++;
do
{
k = st.top();
st.pop();
inst[k] = ;
belong[k] = bcnt; }
while(k != i);
} }
void tarjans(int n)
{
int i;
bcnt = time = ;
while(!st.empty())st.pop();
memset(dfn,,sizeof(dfn)); memset(inst,,sizeof(inst));
memset(belong,,sizeof(belong));
for(i = ;i <= n;i++)
if(!dfn[i])tarjan(i);
}
不考虑重边、
struct edge
{
int u,v,val;
};
int dfn[],low[],belong[],inst[];
int pnum[];
int in[];
int inside[];
int out[];
vector<edge> edges,es;
vector<int>g[maxn];
vector<int>ng[maxn];
stack<int>st;
int bcnt,cnt,dfsclock;
int max(int a,int b)
{
if(a > b)
return a; return b;
}
void init(int n)
{
int i;
for(i =;i <= n;i++)
g[i].clear(); edges.clear(); es.clear();
dfsclock = ;bcnt = cnt = ;
return ;
}
void addedge(int u,int v,int val)
{
edges.push_back((edge){u,v,});
g[u].push_back(cnt);
cnt++; return ;
}
void tarjan(int i)
{
int j;
dfn[i] = low[i] = ++dfsclock;
inst[i] = ;
st.push(i); for(j = ;j < g[i].size();j++)
{
edge e;
e = edges[g[i][j]];
int v;
v = e.v;
if(!dfn[v])
{
tarjan(v);
low[i] = min(low[i],low[v]);
}
else if(inst[v] && dfn[v] < low[i])
low[i] = dfn[v];
}
if(dfn[i] == low[i])
{
bcnt++;
do
{
j = st.top();
st.pop();
inst[j] = ;
belong[j] = bcnt; }
while(j != i);
} }
void tarjans(int n)
{
int i;
bcnt = dfsclock = ;
while(!st.empty())st.pop();
memset(dfn,,sizeof(dfn)); memset(inst,,sizeof(inst));
memset(belong,,sizeof(belong));
for(i = ;i <= n;i++)
if(!dfn[i])tarjan(i);
}
对于双连通分支，包括点连通和边连通。
对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。
对于边双连通分支，求法更为简单。只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。
我的代码（太困了，先贴上睡觉去）
边连通
void tarjan(int u,int pre)
{
int v,i,j;
dfn[u] = low[u] = ++dfsclock;
s.push(u);
loop(,i,g[u].size())
{
v = g[u][i]; if(v != pre)
{
if(!dfn[v])//保证是树枝边
{
tarjan(v,u); low[u] = min(low[v],low[u]); }
else if(dfn[v] < low[u])
low[u] = dfn[v];
} }
if(low[u] ==dfn[u])
{
bcc_cnt++;
int t;
do
{ t = s.top();
s.pop();
belong[t] = bcc_cnt;
}
while(t != u);
}
} void find_bcc(int n)
{
int i;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low)); memset(belong,,sizeof(belong));
while(!s.empty())s.pop();
dfsclock = bcc_cnt = ;
loop(,i,n)
if(!dfn[i]) tarjan(i,-);
// puts("yes");
// printf("%d """"""\n",bcc_cnt);
}
点连通（好吧，这个代码其实是白书上的。明天自己写一个= =。太困了。。。）
int dfs(int u,int fa)
{
int lowu= pre[u]=++dfsclock;
int child=;
for(int i=;i<g[u].size();i++)
{
int v=g[u][i];
edge e;
e.u=u,e.v=v;
if(!pre[v])
{
st.push(e);
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if(lowv>=pre[u])
{
iscut[u]=;
bcc_cnt++;
bcc[bcc_cnt].clear();
for(;;)
{
edge x=st.top();st.pop();
if(bccno[x.u]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(x.u);
bccno[x.u]=bcc_cnt;
}
if(bccno[x.v]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(x.v);
bccno[x.v]=bcc_cnt;
}
if(x.u==u&&x.v==v)break;
}
}
}
else if(pre[v]<pre[u]&&v!=fa)
{
st.push(e);
lowu=min(lowu,pre[v]);
}
}
if(fa<&&child==)iscut[u]=;
return lowu;
}
void find_bcc(int n)
{
int i;
memset(pre,,sizeof(pre));
cl(iscut,);
cl(bccno,);
dfsclock = bcc_cnt = ;
loop(,i,n)
if(!pre[i]) dfs(i,-);
// puts("yes");
// printf("%d """"""\n",bcc_cnt);
}
过两天把这几次的题搞上去吧~