HDU 4612 邊雙連通分量縮點 + 樹的直徑

Problem Description

　　N planets are connected by M bidirectional channels that allow instant transportation. It’s always possible to travel between any two planets through these channels.

　　If we can isolate some planets from others by breaking only one channel , the channel is called a bridge of the transportation system.

People don’t like to be isolated. So they ask what’s the minimal number of bridges they can have if they decide to build a new channel.

　　Note that there could be more than one channel between two planets.

Input

　　The input contains multiple cases.

　　Each case starts with two positive integers N and M , indicating the number of planets and the number of channels.

　　(2<=N<=200000, 1<=M<=1000000)

　　Next M lines each contains two positive integers A and B, indicating a channel between planet A and B in the system. Planets are numbered by 1…N.

　　A line with two integers ‘0’ terminates the input.

Output

　　For each case, output the minimal number of bridges after building a new channel in a line.

Sample Input

4 4

1 2

1 3

1 4

2 3

0 0

Sample Output

題意&&解法：

給你一個n個點m條邊的無向無權圖，問你在添加一條邊的情況下最少有多少條橋。

首先該題存在重邊，又因為當某一條邊存在重邊時則它一定不是橋，故重邊的存在對求橋有影響，是以我們不得不處理重邊。我所知道的有兩種處理重邊的方法，一種通過記錄邊的編号，另一種則是通過隻走一次父邊來處理，我個人比較推薦後者(寫起來友善)。

處理完重邊後我們隻需要用Tarjan邊連通分量縮點 ，縮點後的新圖則是一顆樹(記作T)。容易發現最終所求答案為原圖中橋的數量 - T的直徑。

多說兩句：

求邊連通分量時可以用人們常用的壓棧的方法，也可以采用“能不走橋就不走橋”的染色方法。

ACODE:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef unsigned long long ll;
const int MX = 4e5 + 7;
const int MXM = 2e6 + 7;
inline ll read() {
 	ll a = 0; int f = 0; char p = getchar();
 	while (!isdigit(p)) { f |= p == '-'; p = getchar(); }
 	while (isdigit(p)) { a = (a << 3) + (a << 1) + (p ^ 48); p = getchar(); }
 	return f ? -a : a;
}

inline void write(ll x) {
 	if (x < 0) putchar('-'), x = -x;
 	if (x > 9) write(x / 10);
 	putchar(x % 10 + '0');
}
int n,m;
int tim,tot,num;//分别為時間戳 邊連通分量個數 橋的個數
int head1[MX],cnt1;
int head2[MX],cnt2;

int DFN[MX],LOW[MX];
int col[MX]，par[MX];

bool cut[MX],vis[MX];
int dis[MX];

struct Edge
{
    int v,next;
}G[MXM],NG[MXM];//分别為原圖和縮點後的新圖
inline void add1(int u,int v)
{
    G[++cnt1].v = v;
    G[cnt1].next = head1[u];
    head1[u] = cnt1;
}
inline void add2(int u,int v)
{
    NG[++cnt2].v = v;
    NG[cnt2].next = head2[u];
    head2[u] = cnt2;
}
struct tarjan{
	//初始化
    void init(){
        num = tim = tot = 0;
        cnt1 = cnt2 = 0;
        for(int i = 1;i <= n;++i){
            head1[i] = head2[i] = 0;
            par[i] = i;
            dis[i] = DFN[i] = LOW[i] = 0;
            vis[i] = cut[i] = false;
        }
    }

    inline void dfs(int u,int fa){
        par[u] = fa;
        DFN[u] = LOW[u] = ++tim;
        bool flag = true;//處理重邊的标記
        for(int i = head1[u];i;i = G[i].next){
            int v = G[i].v;
            //處理重邊
            if(flag && v == fa){flag = false;continue;}
            if(!DFN[v]){
                dfs(v,u);
                LOW[u] = min(LOW[u],LOW[v]);
                //求橋 cut[v] 表示節點v - fa 這條邊為橋
                if(LOW[v] > DFN[u]) cut[v] = true,num++;
            }
            else  LOW[u] = min(LOW[u],DFN[v]);
        }
    }
    void pre(){
        dfs(1,-1);
    }

    inline void cdfs(int u){
        vis[u] = true;
        col[u] = tot;
        for(int i = head1[u];i;i = G[i].next){
            int v = G[i].v;
            //如果通路過/該邊為橋 則跳過
            if(vis[v] || (cut[v] && par[v] == u)) continue;
            cdfs(v);
        }
    }

    //邊連通分量染色
    void color(){
        for(int i = 1;i <= n;++i){
            if(!vis[i]) ++tot,cdfs(i);
        }
    }

    //邊連通分量縮點
    void shrink(){
        for(int u = 1;u <= n;++u){
            for(int i = head1[u];i;i = G[i].next){
                int v = G[i].v;
                if(col[u] != col[v]){
                    add2(col[u],col[v]);
                }
            }
        }
    }

    //兩次bfs求樹的直徑
    int bfs(int u){
        for(int i = 1;i <= tot;++i) vis[i] = false;
        queue<int>q;
        q.push(u);
        vis[u] = true;
        dis[u] = 0;
        int t;
        while(!q.empty()){
            t = q.front();q.pop();
            for(int i = head2[t];i;i = NG[i].next){
                int v = NG[i].v;
                if(vis[v])  continue;
                vis[v] = true;
                dis[v] = dis[t] + 1;
                q.push(v);
            }
        }
        return t;
    }

    //計算答案
    int sol(){
        return (num  - dis[bfs(bfs(1))]);
    }
}Tarjan;
int main(int argc, char const *argv[])
{
    while(~scanf("%d%d",&n,&m) && (n + m)){
        Tarjan.init();//初始化
        for(int i = 1;i <= m;++i){
            int u,v;u = read(),v = read();
            add1(u,v);
            add1(v,u);
        }
        Tarjan.pre();//求橋
        Tarjan.color();//染色
        Tarjan.shrink();//縮點
        int res = Tarjan.sol();
        write(res);
        putchar('\n');
    }
    return 0;
}
           

提供幾組資料：

Input

6 6

1 2

2 3

3 4

4 5

2 6

6 2

7 8

1 2

2 3

3 4

4 5

2 6

6 2

1 3

4 7

5 4

2 1

2 3

2 4

2 5

5 5

2 1

2 3

2 4

2 5

3 4

5 5

1 2

2 3

3 4

3 4

4 5

Output

1

2