uva 10765 Doves and bombs(雙聯通分量)

uva 10765 Doves and bombs(雙聯通分量)

給一個n個點聯通的無向圖，要求的是去掉圖中的某個點後，所形成的連通塊的個數。按形成的連通塊的個數的從多到少 和 點的編號從大到小 輸出前m個結果。

解題思路：

說到解題方法，就要說一下求雙連通分量這個事。

我原來理解雙連通分量，以為其形式必然會是 幾個點圍成一個環才能叫一個雙連通分量。其實不然。

定義：在無向連通圖中，如果刪除該圖的任何一個結點都不能改變該圖的連通性，則該圖為雙連通的無向圖。

如果有兩個點a,b相連，那麼a-b就是一個雙聯通分量。它符合上面的定義。並且在這個圖中，其實有兩條邊，a-b和b-a。

這麼看來，也就能理解我在輸出一個圖中所有的雙連通分量時，那些並不構成環的有兩個點組成的邊也能作為一個雙聯通分量輸出。 也才能理解為什麼這道題目可以用求雙連通分量的方法這麼做

解題思路：

如果這個點是割點，這個點必然會出現在多個聯通分量中。那麼去掉這個點，會形成>=兩個連通塊。

如果不是割點，那去掉這個點並不會有更多的連通塊出現。注意這個時候，應該是1個連通塊而不是0個。

這樣我們首先求出所有的連通分量保存下來(bcc[maxn]),然後遍歷所有的雙連通分量，對每一個雙連通分量其中的每一個點都判斷其是否為割點（iscut[x]），如果是，那麼其形成的連通塊個數就+1(ans[x].num++);

code:

#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn = 10005;

//int n,k;
struct node{
    int id;
    int num;
    bool operator<(const node et) const{
        if(num != et.num) return num > et.num;
        else return id < et.id;
    }
}ans[maxn];


int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;
///bccno 是每個節點所屬的雙連通分量的編號
///bcc_cnt是雙連通分量的個數
vector G[maxn], bcc[maxn];
///bcc[]數組記錄了每一支雙連通分量

struct Edge{
    int u, v;
};

stack S;

int dfs(int u, int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i=0; i= pre[u]){
                iscut[u] = true;
                bcc_cnt++; bcc[bcc_cnt].clear();
                for(;;){
                    Edge x = S.top(); S.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){
            S.push(e);
            lowu = min(lowu, pre[v]);
        }
    }
    if(fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}

void find_bcc(int n){
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cnt = 0;
    for(int i=0; i