題意：求出割點(diǎn)以及除去割點(diǎn)后的連通分量的數(shù)量(附帶求出了點(diǎn)雙連通分量(塊)) [求割點(diǎn)]對(duì)圖深度優(yōu)先搜索，定義DFS(u)為u在搜索樹（以下簡(jiǎn)稱為樹）中被遍歷到的次序號(hào)。定義Low(u)為u或u的子樹中能通過非父子邊追溯到的最早的節(jié)點(diǎn)，即DFS序號(hào)最小的節(jié)點(diǎn)。根據(jù)定義，則有：Low(u)=Min {DFS(u),DFS(v)|(u,v)為后向邊(等價(jià)于DFS(v)<DFS(u)且v不為u的父親節(jié)點(diǎn)),Low(v)|(u,v)為樹枝邊} [條件]一個(gè)頂點(diǎn)u是割點(diǎn)，當(dāng)且僅當(dāng)滿足(1) u為樹根，且u有多于一個(gè)子樹。或(2) u不為樹根，且滿足存在(u,v)為樹枝邊(即u為v在搜索樹中的父親)，使得DFS(u)<=Low(v)。 [除去點(diǎn)后的連通分量的]：對(duì)于(1)的割點(diǎn)，數(shù)量為子樹的數(shù)量；(2)的數(shù)量就是滿足條件的v的個(gè)數(shù)+1(它的父親節(jié)點(diǎn)). [求點(diǎn)雙連通分支]對(duì)于點(diǎn)雙連通分支，實(shí)際上在求割點(diǎn)的過程中就能順便把每個(gè)點(diǎn)雙連通分支求出。建立一個(gè)棧，存儲(chǔ)當(dāng)前雙連通分支，在搜索圖時(shí)，每找到一條樹枝邊或后向邊，就把這條邊加入棧中。如果遇到某時(shí)滿足DFS(u)<=Low(v)，說明u是一個(gè)割點(diǎn)，同時(shí)把邊從棧頂一個(gè)個(gè)取出，直到遇到了邊(u,v)，取出的這些邊與其關(guān)聯(lián)的點(diǎn)，組成一個(gè)點(diǎn)雙連通分支。割點(diǎn)可以屬于多個(gè)點(diǎn)雙連通分支，其余點(diǎn)和每條邊只屬于且屬于一個(gè)點(diǎn)雙連通分支。 ? #include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std;const int MAXE = 1000005; const int MAXV = 1005; struct node{int u, v;int next; }arc[MAXE]; int cnt, head[MAXV]; void init(){cnt = 0;mem(head, -1); } void add(int u, int v){arc[cnt].u = u;arc[cnt].v = v;arc[cnt].next = head[u];head[u] = cnt++;arc[cnt].u = v;arc[cnt].v = u;arc[cnt].next = head[v];head[v] = cnt++;return ; }int id, dfn[MAXV], low[MAXV]; //時(shí)間戳 int bcc_num; //點(diǎn)雙聯(lián)通分量標(biāo)號(hào) vector bcc[MAXV]; //因?yàn)楦铧c(diǎn)可以屬于多個(gè)雙聯(lián)通分量，所以用數(shù)組存儲(chǔ)每個(gè)雙聯(lián)通分量的節(jié)點(diǎn)而不是用標(biāo)號(hào)數(shù)組表示每個(gè)節(jié)點(diǎn)所屬的雙聯(lián)通分量 stack st; //棧中存著樹枝邊或后向邊 int res[MAXV]; //本題所求答案,即割點(diǎn)連接的雙聯(lián)通分量個(gè)數(shù),樹根是子樹個(gè)數(shù),非樹根是子樹個(gè)數(shù)+1. void addbcc(int bcc_num, int u){for (int i = 0; i < (int)bcc[bcc_num].size(); i ++){if (bcc[bcc_num][i] == u)return ;}bcc[bcc_num].push_back(u); } void tarjan(int u, int father){dfn[u] = low[u] = ++id;int child = 0;for (int i = head[u]; i != -1; i = arc[i].next){int v = arc[i].v;if (v == father) continue;if (dfn[v] < dfn[u]){ //避免正向邊st.push(i);if (!dfn[v]){ //樹枝邊child ++; //注意這里統(tǒng)計(jì)兒子節(jié)點(diǎn)時(shí)不要寫在if外面tarjan(v, u);low[u] = min(low[u], low[v]);if (dfn[u] <= low[v]){bcc_num ++;res[u] ++; //非樹根節(jié)點(diǎn)連接的雙聯(lián)通分量個(gè)數(shù)while(!st.empty()){int su = arc[st.top()].u;int sv = arc[st.top()].v;st.pop();addbcc(bcc_num, su);addbcc(bcc_num, sv);if((su == u && sv == v) || (su == v && sv == u)){break;}}}}else{ //后向邊low[u] = min(low[u], dfn[v]);}}}//統(tǒng)計(jì)割點(diǎn)連接的雙聯(lián)通分量個(gè)數(shù)if (father == 0){if (child >= 2){ //樹根大于一個(gè)子樹才是割點(diǎn)res[u] = child;}elseres[u] = 0;}else if (res[u] > 0) //非樹根除了子樹個(gè)數(shù)還要加上父親節(jié)點(diǎn)res[u] ++; } void solve(){id = bcc_num = 0;mem(dfn, 0);mem(low, 0);mem(res, 0);while(!st.empty())st.pop();tarjan(1, 0); } int main(){int u, v;int t = 0;while(scanf("%d", &u) == 1){init();++ t;if (u == 0)break;if (t > 1)puts("");scanf("%d", &v);add(u, v);while(scanf("%d", &u) == 1){if (u == 0)break;scanf("%d", &v);add(u, v);}solve();bool flag = 0;printf("Network #%d\n", t);for (int i = 1; i <= MAXV; i ++){if (res[i] > 0){printf(" SPF node %d leaves %d subnets\n", i, res[i]);flag = 1;}}if (!flag){puts(" No SPF nodes");}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/AbandonZHANG/archive/2013/05/30/4114026.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的POJ 1523 SPF (割点 点双连通分量)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。