原题链接
建补图，这样题目要求的即是求有多少个点没有被任何奇环包含。
这里有两个结论：
- 若两个骑士属于两个不同的(v-DCC)，那么这两个骑士肯定不能一起出席会议。
- 若在某个(v-DCC)中，存在一个奇环，那么该点双连通分量中所有点都被至少一个奇环包含。
所以，我们只需要在用(tarjan)求(v-DCC)的过程中，判断每个(v-DCC)是否包含奇环，若包含奇环，那么该(v-DCC)里所有骑士都可以出席会议。
判断奇环可以使用染色法，因为一个奇环中必定有一对相邻点的颜色相同。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
const int M = 1e6 + 10;
int a[N][N], fi[N], di[M << 1], ne[M << 1], st[N], dfn[N], low[N], co[N], v[N], DCC[N], l, tp, ti, d, v_DCC;
bool jo[N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + (c - '0');
return p ? -x : x;
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
inline void add(int x, int y)
{
di[++l] = y;
ne[l] = fi[x];
fi[x] = l;
}
bool dfs(int x, int c)
{
int i, y;
bool p = false;
co[x] = c;
for (i = fi[x]; i; i = ne[i])
{
y = di[i];
if (!(v[y] ^ v_DCC))
{
if (!co[y])
p = dfs(y, c ^ 1);
else
if (!(co[y] ^ c))
return true;
}
}
return p;
}
void tarjan(int x)
{
int i, j, y, z;
dfn[x] = low[x] = ++ti;
st[++tp] = x;
for (i = fi[x]; i; i = ne[i])
{
y = di[i];
if (!dfn[y])
{
tarjan(y);
low[x] = minn(low[x], low[y]);
if (low[y] >= dfn[x])
{
++v_DCC;
d = 0;
do
{
z = st[tp--];
v[z] = v_DCC;
DCC[++d] = z;
co[z] = 0;
} while (z ^ y);
v[x] = v_DCC;
co[x] = 0;
DCC[++d] = x;
if (dfs(x, 2))
for (j = 1; j <= d; j++)
jo[DCC[j]] = 1;
}
}
else
low[x] = minn(low[x], dfn[y]);
}
}
int main()
{
int i, n, m, j, x, y, s;
while (1)
{
s = n = re();
m = re();
if (!n && !m)
return 0;
memset(a, 0, sizeof(a));
memset(fi, 0, sizeof(fi));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(v, 0, sizeof(v));
memset(jo, 0, sizeof(jo));
l = ti = v_DCC = tp = 0;
for (i = 1; i <= m; i++)
{
x = re();
y = re();
a[x][y] = a[y][x] = 1;
}
for (i = 1; i < n; i++)
for (j = i + 1; j <= n; j++)
if (!a[i][j])
{
add(i, j);
add(j, i);
}
for (i = 1; i <= n; i++)
if (!dfn[i])
{
if (!fi[i])
continue;
tarjan(i);
}
for (i = 1; i <= n; i++)
if (jo[i])
s--;
printf("%d
", s);
}
return 0;
}