題目大意

有N個(gè)騎士，給出某些騎士之間的仇恨關(guān)系，每次開會(huì)時(shí)會(huì)選一些騎士開，騎士們會(huì)圍坐在一個(gè)圓桌旁。一次會(huì)議能夠順利舉行，要滿足兩個(gè)條件：1.任意相互憎恨的兩個(gè)騎士不能相鄰。2.開會(huì)人數(shù)為大于2的奇數(shù)。若某個(gè)騎士任何會(huì)議都不能參加，那么就必須將他踢出，給出騎士之間的仇恨關(guān)系，問最少需要踢出多少個(gè)騎士？

總體思路

依題意，把騎士看作節(jié)點(diǎn)，每個(gè)騎士向其不仇視的騎士連一條無向邊。如果一個(gè)騎士所代表的節(jié)點(diǎn)在一個(gè)奇環(huán)內(nèi)，則該騎士便可以與環(huán)內(nèi)節(jié)點(diǎn)所代表的騎士一起開會(huì)，所以我們要找到那個(gè)奇環(huán)。

我們要先找到環(huán)，再看看它是不是奇的。

利用的性質(zhì)

• 圖中所有的環(huán)包含在圖的點(diǎn)雙連通分量中（因?yàn)榄h(huán)中不存在割點(diǎn)）（圖的點(diǎn)雙連通分量為圖的極大不存在割點(diǎn)的子圖）。
• 如果一個(gè)雙連通分量中存在奇環(huán)，則該雙連通分量中的所有節(jié)點(diǎn)都屬于一個(gè)奇環(huán)（如果存在一個(gè)奇環(huán)，則該雙連通分量中的其它節(jié)點(diǎn)必由兩條路徑與奇環(huán)中的兩個(gè)節(jié)點(diǎn)相連（否則路徑上就有割點(diǎn)了）。兩個(gè)節(jié)點(diǎn)之間因?yàn)樵谄姝h(huán)中，所以連接兩節(jié)點(diǎn)奇環(huán)內(nèi)必有兩條路徑，一條是奇的，一條是偶的。因?yàn)榻?jīng)過那個(gè)其它節(jié)點(diǎn)與這兩個(gè)節(jié)點(diǎn)的路徑長(zhǎng)度是固定的，所以命題成立）。

求點(diǎn)雙連通分量：Tarjan ——的一種方法

在基本Tarjan算法的基礎(chǔ)上構(gòu)造一個(gè)維護(hù)節(jié)點(diǎn)的棧，其保證棧內(nèi)節(jié)點(diǎn)cur和cur以上的所有節(jié)點(diǎn)都位于一個(gè)或多個(gè)雙連通分量中。如果cur是割點(diǎn)，使得cur是某個(gè)遍歷出的相鄰節(jié)點(diǎn)v所屬的雙連通分量中DfsN值最小的節(jié)點(diǎn)，則一直將棧內(nèi)v及以上的所有節(jié)點(diǎn)和cur納入一個(gè)雙連通分量中，將v及以上所有節(jié)點(diǎn)出棧。

注意事項(xiàng)

• 永遠(yuǎn)記住如果cur是割點(diǎn)不代表所有與cur相鄰的節(jié)點(diǎn)都屬于不同的雙連通分量！所以是出棧到v，而不是出棧到cur。
• 即使cur是根節(jié)點(diǎn)且cnt<1（其實(shí)在此題中cnt根本不需要），也要進(jìn)行出棧操作，因?yàn)榇怂惴ㄊ且贿叡闅v一邊設(shè)雙連通分量，如果根遍歷到的第一個(gè)v節(jié)點(diǎn)便與根屬于一個(gè)雙連通分量，cnt不小于1導(dǎo)致了跳過。
• 記住判斷割點(diǎn)的依據(jù)是cur->DfsN <= v->Low，而不是cur->DfsN <= cur->Low。
• 根節(jié)點(diǎn)可能不是割點(diǎn)，但是根節(jié)點(diǎn)必須在一個(gè)點(diǎn)雙連通分量中，所以要注意Dfs完后的出棧操作。

判斷奇環(huán)——二分圖判定

利用染色的方法，將節(jié)點(diǎn)分為黑白兩種顏色，一個(gè)節(jié)點(diǎn)要嘗試將下一個(gè)節(jié)點(diǎn)染成與自己不同的顏色。如果下一個(gè)節(jié)點(diǎn)已有與自己相同的顏色，則此非二分圖，存在奇環(huán)。如果最終得到了一個(gè)二分圖，則不存在奇環(huán)。

?

AC待優(yōu)化代碼：

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std;#define LOOP(i,n) for(int i=1; i<=n; i++) const int MAX_NODE = 5000, MAX_EDGE = 1000010 * 2;struct Node; struct Edge;struct Node {int Id, DfsN, Low, Color;bool InBlock, InTable;//inTable:能加入圓桌會(huì)議Edge *Head; }_nodes[MAX_NODE];struct Edge {Node *From, *To;Edge *Next, *Rev;Edge(){}Edge(Node *from, Node *to, Edge *next):From(from),To(to),Next(next){} }*_edges[MAX_EDGE];int _vCount, _eCount, DfsCnt; vector<vector<Node*>> Blocks; vector<Node*> Stack;void Init(int n) {memset(_nodes, 0, sizeof(_nodes));_eCount = DfsCnt = 0;Blocks.clear();Stack.clear();_vCount = n; }Edge *NewEdge(Node *from, Node *to, Edge *next) {_eCount++;if (_edges[_eCount])*_edges[_eCount] = Edge(from, to, next);else_edges[_eCount] = new Edge(from, to, next);return _edges[_eCount]; }Edge *AddEdge(Node *from, Node *to) {Edge *e = NewEdge(from, to, from->Head);from->Head = e;return e; }void Build(int uId, int vId, bool is2d) {Node *u = uId + _nodes, *v = vId + _nodes;u->Id = uId;v->Id = vId;Edge *e1 = AddEdge(u, v);if (is2d) {Edge *e2 = AddEdge(v, u);e1->Rev = e2;e2->Rev = e1;} }void DeStack(Node *cut, Node *v) {Node *blockMember;vector<Node*> newBlock;Blocks.push_back(newBlock);while(!Stack.empty()) {//易忘點(diǎn)blockMember = Stack.back();Blocks.back().push_back(blockMember);Stack.pop_back();if (blockMember == v)break;};if (cut != NULL)Blocks.back().push_back(cut); }void Dfs(Node *u,Node *root) {u->DfsN = u->Low = ++DfsCnt;Stack.push_back(u);for (Edge *e = u->Head; e; e = e->Next) {if (!e->To->DfsN) {Dfs(e->To,root);u->Low = min(u->Low, e->To->Low);if (u->DfsN <= e->To->Low)DeStack(u, e->To);}elseu->Low = min(u->Low, e->To->DfsN);} }void SetBlock() {for (int i = 1; i <= _vCount; i++) {if (!_nodes[i].DfsN) {Stack.clear();Node *root = i + _nodes;Dfs(root, root);if (!Stack.empty())DeStack(root, NULL);}} }bool HaveOrdCircle(Node *u, int curColor) {u->Color = curColor;for (Edge *e = u->Head; e; e = e->Next) {if (e->To->InBlock) {if (e->To->Color == -1) {if (HaveOrdCircle(e->To, !curColor))return true;}else if (e->To->Color == curColor)return true;}}return false; }void SetTableMember() {int blockCnt = Blocks.size();for (int i = 0; i < blockCnt; i++) {int nodeCnt = Blocks[i].size();if (nodeCnt <= 2)continue;for (int j = 0; j < nodeCnt; j++) {Blocks[i][j]->InBlock = true;Blocks[i][j]->Color = -1;}for (int j = 0; j < nodeCnt; j++)if (HaveOrdCircle(Blocks[i][0], 0))for (int j = 0; j < nodeCnt; j++)Blocks[i][j]->InTable = true;for (int j = 0; j < nodeCnt; j++)Blocks[i][j]->InBlock = false;} }int main() { #ifdef _DEBUGfreopen("c:\\noi\\source\\input.txt", "r", stdin);freopen("c:\\noi\\source\\output.txt", "w", stdout); #endifstatic bool hate[MAX_NODE][MAX_NODE];int totNode, totHate, a, b;while (~scanf("%d%d", &totNode, &totHate) && (totNode || totHate)) {Init(totNode);memset(hate, false, sizeof(hate));for (int i = 1; i <= totHate; i++) {scanf("%d%d", &a, &b);hate[a][b] = hate[b][a] = true;}for (int i = 1; i <= totNode; i++)for (int j = 1; j <= totNode; j++)if (i != j && !hate[i][j])Build(i, j, false);SetBlock();SetTableMember();int cnt = 0;for (int i = 1; i <= _vCount; i++)if (!_nodes[i].InTable)cnt++;printf("%d\n", cnt);}return 0; }

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/headboy2002/p/8471238.html

總結(jié)

以上是生活随笔為你收集整理的POJ2942 Knights of the Round Table 点双连通分量 二分图判定的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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