程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 10765 Doves and bombs(雙聯通分量)

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

編輯:C++入門知識

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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved