这道题的意思是,一群武士,某些武士之间相互仇视,在一起会发生争斗事件,因此只有满足一定条件才能够参加圆桌会议。首先是圆桌上相邻的两个武士不能有仇,同一个圆桌上的武士数量必须是奇数,而且大于2。最后求完全不可能参加会议的武士的数量。
那么可以联想到转化为一个无向图,各个武士看成顶点,互相没仇的武士之间建边,表示可以坐在一块,
建立无向图后,所有能坐在一起的武士分为一组,这一组在图中必然就是一个双连通分量,因为在一个结点大于2的双连通分量中,必然存在一个圈经过连通分量的所有点,这样就表示形成了一个圆桌,并且这个圈应该是奇圈,判奇圈的方式用的是交叉染色,意思也很好理解,假如在一个圆桌上,从某一个人开始,进行1,2报数,那么如果人的个数是奇数,最后一个人和第一个人报的数必然是一样的。这个实际上就是判断是不是二分图,因为二分图内是不存在奇圈的。如果用其他的方法就比较不好实现,比如数圈上结点的个数,听起来很简单,但是做起来还是难以实现。
求重连通分量的方法,就是在求割点的基础上进行的,建立一个栈,存储当前重连通分量,在DFS过程中,每找到一个边或回边,就把这条边加入栈中,如果遇到某个顶点u的子女v满足low[v] >= dfn[u] ,说明u为割点,同时把边从栈顶一条条的取出,直到遇到了边(u, v),这些取出的边便组成了一个重连通分量。
需要注意的是,要开一个二维数组记录边是否访问过,访问过就不能再访问了,如果不记录,在POJ会WA掉。但是如果仅仅用程序来求割点,而不求重连通分量,记录不记录边是否访问过好像就没有影响了。
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 1005
#define MAXM 1000005
#define INF 1000000000
using namespace std;
int n, m;
int mp[MAXN][MAXN], e, head[MAXN];
int vis[MAXN], ok[MAXN], mark[MAXN], col[MAXN];
int tmpdfn, top, dfn[MAXN], low[MAXN];
struct Edge
{
int v, next;
}edge[MAXM];
struct Stack
{
int s, e;
Stack(){}
Stack(int a, int b){s = a; e = b;}
}st[MAXM];
void init()
{
e = 0, tmpdfn = 0, top = -1;
memset(mp, 0, sizeof(mp));
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(ok, 0, sizeof(ok));
}
void insert(int x, int y)
{
edge[e].v = y;
edge[e].next = head[x];
head[x] = e++;
}
void ReadData()
{
int u, v;
while(m--)
{
scanf("%d%d", &u, &v);
mp[u][v] = mp[v][u] = -1;
}
}
void build()
{
ReadData();
for(int i = 1; i <= n; i++)
{
mp[i][i] = -1;
for(int j = 1; j <= n; j++)
if(mp[i][j] == 0) insert(i, j);
}
}
bool can(int u)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(mark[v])
{
if(col[v] == -1){col[v] = !col[u]; return can(v);}
else if(col[v] == col[u]) return 1;
}
}
return 0;
}
void color(int u, Stack t)
{
memset(mark, 0, sizeof(mark));
memset(col, -1, sizeof(col));
col[u] = 0;
while(top >= 0)
{
Stack A = st[top--];
mark[A.s] = mark[A.e] = 1;
if(A.s == t.s && A.e == t.e) break;
}
if(can(u))
for(int i = 1; i <= n; i++)
if(mark[i]) ok[i] = 1;
}
void dfs(int u, int fa)
{
vis[u] = 1;
dfn[u] = low[u] = ++tmpdfn;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(mp[u][v] == 0)
{
mp[u][v] = mp[v][u] = 1;
Stack tmp(u, v);
st[++top] = tmp;
if(!vis[v])
{
dfs(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) color(u, tmp);
}
else if(v != fa) low[u] = min(low[u], dfn[v]);
}
}
}
void solve()
{
for(int i = 1; i <= n; i++)
if(!vis[i]) dfs(i, 0);
int ans = 0;
for(int i = 1; i <= n; i++)
if(!ok[i]) ans++;
printf("%d\n", ans);
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
if(n == 0 && m == 0) break;
init();
build();
solve();
}
return 0;
}
分享到:
相关推荐
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ2151-Check the difficulty of problems 解题报告+AC代码
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
poj 3174 Alignment of the Planets.md
北大POJ3252-Round Numbers 解题报告+AC代码
北大POJ3083-Children of the Candy Corn 解题报告+AC代码
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1163-The Triangle
北大POJ3239-Solution to the n Queens Puzzle 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ3267-The Cow Lexicon 解题报告+AC代码
poj 1611 The Suspects 代码 并查集的应用
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码