上一场吉林大学的多校，多题用到联通性的low，dfn性质，但是都木有做出来。。。
题目描述：
一群骑士，某些骑士之间互相憎恨，如果在一起容易发生争斗事件，因此他们只有满足一定条件才能参加圆桌会议：1.圆桌边上任意相邻的两个骑士不能互相憎恨；2。同一个圆桌边上的骑士数量必须是奇数；
解题报告：
1
骑士ij连边（无向边），表示这两个骑士没有憎恨关系（可以坐在一起）。
2
这样建图后，实质是问每个骑士能否在一个奇环内即可。
3
然后按照点双连通分块，容易知道，如果i骑士能分在一个奇环内，这个环一在i骑士所在的块内。
4
此时问题转化为：在块内找奇环。
5
有一条很好的性质：如果这个块内，只要存在一个奇环（不管这个环有多少的点），那么这个块的所有点都可以被奇环包围。
6
那么奇环很好判断：二分图染色后，只要有一个点和它的相邻节点的颜色相同，就找到了奇环。
代码如下：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
#define SIZE 1004
int n, m, G[SIZE][SIZE];
//tarjan template
vector<int> v[SIZE];
vector<int>
block[SIZE];//块
int dfn[SIZE], low[SIZE], sta[SIZE], top, index, cnt;
int root;//特判根节点是否是割点
bool instack[SIZE], iscut[SIZE];//是否是割点;
void tarjan(int id, int fa)
{
dfn[id]
= low[id] = ++index;
sta[top++] = id; instack[id] = true;
bool
flag = false;
for(int
i = 0; i < v[id].size(); i++)
if (v[id][i] == fa
&& !flag) flag = true;
else if (!dfn[v[id][i]])
{
int to = v[id][i];
tarjan(to, id);
if (low[to] < low[id]) low[id] =
low[to];
if (low[to] >=
dfn[id])//id是割点
{
if (fa ==
-1) root++;//特判根节点
else
iscut[id] = true;
int
tmp;do
{
tmp = sta[--top]; instack[tmp]
= 0;
block[cnt].push_back(tmp);
}while(tmp
!= to);
block[cnt].push_back(id);
cnt++;
}
}else if (instack[v[id][i]]
&& dfn[v[id][i]] <
low[id])
low[id] = dfn[v[id][i]];
}
void solve(int n)
{
memset(instack, 0, sizeof(instack));
cnt =
index = top = 0;
memset(dfn, 0, sizeof(dfn));
memset(iscut, 0, sizeof(iscut));
for(int
i = 0; i < n; i++)
block[i].clear();//block始终从0记
for(int
i = 1; i <= n; i++)//这里从1从0看具体要求
if (!dfn[i])
{
root = 0;
tarjan(i, -1);
if (root > 1) iscut[i] =
true;
}
}
int col[SIZE], vst[SIZE];
void color(int id, int co, int tar)
{
col[id]
= co;
vst[id]
= 0;
for(int
i = 0; i < v[id].size(); i++) if (vst[v[id][i]] ==
tar)
color(v[id][i], co ^ 1,
tar);
}
int jeo[SIZE];
int jeogia()
{
int ans
= 0;
memset(jeo, 0, sizeof(jeo));
for(int
i = 0; i < cnt; i++)
{
for(int j = 0; j
< block[i].size(); j++)
vst[block[i][j]] = (-10 - i);
color(block[i][0], 0, -10 -
i);
bool flag = false;
for(int j = 0; j
< block[i].size(); j++)
vst[block[i][j]] = (-10 - i);
for(int j = 0; j
< block[i].size(); j++)
{
int id = block[i][j];
for(int k = 0; k < v[id].size();
k++)
if
(v[id][k] != id && vst[v[id][k]] ==
(-10 - i) && col[id] ==
col[v[id][k]])
{flag =
true;break;}
if (flag) break;
}
if (flag)
for(int j = 0; j <
block[i].size(); j++)
jeo[block[i][j]] = 1;
}
for(int
i = 1; i <= n; i++) if (!jeo[i]) ans++;
return
ans;
}
int main()
{
while(scanf("%d%d", &n,
&m) && (n ||
m))
{
for(int i = 1; i
<= n; i++) v[i].clear();
memset(G, 0, sizeof(G));
for(int i = 0; i
< m; i++)
{
int a, b;scanf("%d%d", &a,
&b);
G[a][b] = G[b][a] = 1;
}
for(int i = 1; i
<= n; i++) for(int j = 1; j <= n;
j++)
if (!G[i][j]) v[i].push_back(j);
solve(n);
printf("%d\n",
jeogia());
}
return 0;
}
加载中，请稍候......
加载中…
喜欢