一種很簡(jiǎn)潔的寫法，那個(gè)用棧存的算法實(shí)在是比較難看。
問題大概是這樣子的：
無(wú)向圖割點(diǎn)：比較特殊，因?yàn)榭赡茏庸?jié)點(diǎn)從別的路返回到父親點(diǎn)，如果父親點(diǎn)再?gòu)淖约悍祷氐礁叩母赣H點(diǎn)。。所以
low[father] =
minst{
dfn[father],
low[child],
dfn[others]
};
無(wú)向圖割邊:還可以用上面的公式，對(duì)于邊u->v，如果low[v] < dfn[u]，我們可以認(rèn)為這是割邊
無(wú)向圖邊雙聯(lián)通：
low[father] =
minst{
dfn[father],
low[others]，除了返回父親的邊
}
至于為什么會(huì)這樣,畫個(gè)圖理解下就好
有向圖強(qiáng)聯(lián)通：
和無(wú)向圖邊雙聯(lián)通是一樣的,這是不對(duì)的！！還沒想到好的辦法，還得用tarjan算法搞。無(wú)向圖點(diǎn)雙聯(lián)通：
用求割點(diǎn)的那個(gè)公式，dfs把點(diǎn)放到棧里面，當(dāng)dfn[u] == low[u]的時(shí)候出棧，棧里面的點(diǎn)在一個(gè)點(diǎn)雙聯(lián)通里，記得把當(dāng)前點(diǎn)留在棧里
//無(wú)向圖邊雙連通+縮點(diǎn),已知圖是個(gè)聯(lián)通圖
#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;
}