给出一个无向图,然后计算出该图的补图,然后再计算补图中不再任一奇圈内的点的个数。
首先要求出所有的点的双连通分量,然后判断每一个双连通分量中是否存在奇圈,若有,则该双连通分量中的任意一点均在某一个奇圈上。
求解双连通分量的方法:
设 rv[ ] 表示每个点在DFS时被访问的次序,low[ ] 表示节点 u 及其子孙所连接到点中 rv[ ] 最小的值。
首先需要一个辅助栈来存放每一个双连通分量的边。
若边( u , v )仅符合下面两种情况的任意一种则将边压入栈中:
1,v 尚未被访问。
2,rv[ v ] <= low[u] 且 v 正在等待回溯。
若当 u 的 子节点 v 回溯完成时有 low[v] >= rv[u],则说明 u 是一个割点,此时要将栈中的在(u , v )及在其后面压入的边弹出,这些边就组成了一个点的双连通分量。
判断奇圈可以用BFS染色法。可见判断二分图的方法
代码有写的好挫。。。
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <algorithm> #include <stack> #define LL long long #define ULL unsigned long long #define PI (acos(-1.0)) #define EPS (1e-10) #pragma comment(linker,"/STACK:102400000,1024000") using namespace std; const int MAX = (1<<30); struct N { int v,next; }edge[1001000]; int head[1010]; int Top,Dfs_Clock; bool Is_Edge[1010][1010],Is_Cut[1010],InCirle[1010],Wait_Dfs[1010]; int rv[1010],low[1010]; void Link(int u,int v) { edge[Top].v = v; edge[Top].next = head[u]; head[u] = Top++; } struct E { int u,v; }te[1001000]; stack<E> st; int color[1010]; int Top_E; int Knight; void dfs(int u,int fa) { rv[u] = Dfs_Clock; low[u] = Dfs_Clock++; int v; for(int p = head[u];p != -1; p = edge[p].next) { v = edge[p].v; E e = (E){u,v}; if(rv[v] == -1) { st.push(e); dfs(v,u); low[u] = min(low[u],low[v]); if(low[v] >= rv[u]) { Top_E = 0; do { e = st.top(); st.pop(); te[Top_E++] = e; }while(e.u != u || e.v != v); memset(color,-1,sizeof(color)); color[te[0].u] = 1; color[te[0].v] = 0; bool mark = false; bool Is_Circle = false; while(mark == false && Is_Circle == false) { mark = true; for(int i = 0;i < Top_E; ++i) { if(color[te[i].u] == -1 && color[te[i].v] != -1) { color[te[i].u] = (color[te[i].v] == 1 ? 0 : 1); mark = false; } else if(color[te[i].u] != -1 && color[te[i].v] == -1) { color[te[i].v] = (color[te[i].u] == 1 ? 0 : 1); mark = false; } else if(color[te[i].u] != -1 && color[te[i].u] == color[te[i].v]) { Is_Circle = true; } } } if(Is_Circle) { memset(color,-1,sizeof(color)); for(int i = 0;i < Top_E; ++i) { if(color[te[i].u] == -1) { color[te[i].u] = 1; { Knight--; } if(InCirle[te[i].u]) { Knight++; } else { InCirle[te[i].u] = true; } } if(color[te[i].v] == -1) { color[te[i].v] = 1; { Knight--; } if(InCirle[te[i].v]) { Knight++; } else { InCirle[te[i].v] = true; } } } } Is_Cut[u] = true; } } else if(low[v] <= low[u] && v != fa && Wait_Dfs[v] == false) { st.push(e); low[u] = min(low[u],rv[v]); } } Wait_Dfs[u] = true; } int main() { int n,m,i,j,u,v; while(scanf("%d %d",&n,&m) && (n||m)) { for(i = 1;i <= n; ++i) { memset(Is_Edge[i],false,sizeof(bool)*(n+3)); } for(i = 1;i <= m; ++i) { scanf("%d %d",&u,&v); Is_Edge[u][v] = Is_Edge[v][u] = true; } memset(head,-1,sizeof(int)*(n+3)); Top = 0; for(i = 1;i <= n; ++i) { for(j = 1;j < i; ++j) { if(Is_Edge[i][j] == false) { Link(i,j); Link(j,i); } } } memset(rv,-1,sizeof(int)*(n+3)); memset(Is_Cut,false,sizeof(bool)*(n+3)); memset(InCirle,false,sizeof(bool)*(n+3)); memset(Wait_Dfs,false,sizeof(bool)*(n+3)); Dfs_Clock = 0; Knight = n; for(i = 1;i <= n; ++i) { if(rv[i] == -1) { dfs(i,-1); } } printf("%d\n",Knight); } return 0; }
POJ 2942 Knights of the Round Table 点的双连通分量 + 奇圈
原文:http://blog.csdn.net/zmx354/article/details/19295757