一种很简洁的写法,那个用栈存的算法实在是比较难看。
问题大概是这样子的:
无向图割点:比较特殊,因为可能子节点从别的路返回到父亲点,如果父亲点再从自己返回到更高的父亲点。。所以
low[father] =
minst{
dfn[father],
low[child],
dfn[others]
};
无向图割边:还可以用上面的公式,对于边u->v,如果low[v] < dfn[u],我们可以认为这是割边
无向图边双联通:
low[father] =
minst{
dfn[father],
low[others],除了返回父亲的边
}
至于为什么会这样,画个图理解下就好
有向图强联通:
和无向图边双联通是一样的,这是不对的!!还没想到好的办法,还得用tarjan算法搞。无向图点双联通:
用求割点的那个公式,dfs把点放到栈里面,当dfn[u] == low[u]的时候出栈,栈里面的点在一个点双联通里,记得把当前点留在栈里
//无向图边双连通+缩点,已知图是个联通图
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 5010;
int nmap[maxn][maxn];
vector<int> edg[maxn];
int dfn[maxn],vis[maxn],low[maxn];
int deg[maxn];
int N,M;
int t;
void dfs(int p,int i)
{
vis[i] = 1;
dfn[i] = low[i] = ++t;
for(int j = 0;j<edg[i].size();j++)
{
int next = edg[i][j];
if(next == p) continue;
if(!vis[next])
{
dfs(i,next);
}
low[i] = min(low[i],low[next]);
}
vis[i] = 2;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d%d",&N,&M);
int i,a,b;
for(i=0;i<M;i++)
{
scanf("%d%d",&a,&b);
if(nmap[a][b]) continue;
edg[a].push_back(b);
edg[b].push_back(a);
nmap[a][b] = 1;
}
dfs(1,1);
int leaf = 0;
for(i=1;i<=N;i++)
{
for(int j=0;j<edg[i].size();j++)
{
if(low[i] != low[edg[i][j]])
deg[low[i]]++;
}
}
for(i=1;i<=t;i++)
{
if(deg[i] == 1) leaf++;
}
printf("%d\n",(leaf+1)/2);
return 0;
}