很巧的一道点双
两个骑士如果相互憎恨，我们考虑连边的话，不太好处理答案，所以我们尝试一下建反图。
如果两个骑士没有相互憎恨，我们就在他们两个人之间连一条无向边，最后要让你会议召开，那么显然是选择任意一个奇环上的所有点。
现在题目就变成了找不在奇环上的点的个数。
有引理：
-
若两个点属于不同的点双，则他们不可能在同一个奇环。
-
若某个点双内存在奇环，则这个点双的所有点必定被至少一个奇环包含。
综上所述，奇环只会在点双内，所以我们把反图的点双找出来，一个一个判断是否存在奇环即可(只要存在奇环，这个点双内的所有点一定有办法参加会议, 因为总有一个奇环会包含点双内的一些点，这所有奇环的并集就是点双内的所有点)。
对于判断一张图是否存在奇环，实际上就是判断一张图是不是二分图，因为二分图是不可能存在奇环的，存在奇环的图也一定不是二分图。
最后统计不在奇环的点即可。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
int X = 0, w = 0; char ch = 0;
while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans;
}
const int N = 1005;
int n, m, cnt, k, root, tot, head[N], dfn[N], low[N], cut[N], col[N], c[N];
bool has[N][N], able[N], flag;
vector<int> dcc[N];
stack<int> st;
struct Edge { int v, next; } edge[2000005];
void addEdge(int a, int b){
edge[cnt].v = b, edge[cnt].next = head[a], head[a] = cnt ++;
}
void build(){
while(!st.empty()) st.pop();
cnt = k = tot = 0;
full(has, false), full(head, -1);
full(dfn, 0), full(low, 0);
full(cut, false), full(able, false);
full(col, 0), full(c, 0);
for(int i = 1; i <= n; i ++)
dcc[i].clear();
}
void tarjan(int s){
dfn[s] = low[s] = ++k;
st.push(s);
if(s == root && head[s] == -1){
dcc[++tot].push_back(s);
return;
}
int flag = 0;
for(int i = head[s]; i != -1; i = edge[i].next){
int u = edge[i].v;
if(!dfn[u]){
tarjan(u);
low[s] = min(low[s], low[u]);
if(low[u] >= dfn[s]){
flag ++;
if(s != root || flag > 1) cut[s] = true;
tot ++;
int cur;
do{
cur = st.top(); st.pop();
dcc[tot].push_back(cur);
}while(cur != u);
dcc[tot].push_back(s);
}
}
else low[s] = min(low[s], dfn[u]);
}
}
bool dfs(int s, int color, int cur){
col[s] = color;
for(int i = head[s]; i != -1; i = edge[i].next){
int u = edge[i].v;
if(c[u] != cur) continue;
if(col[u] == color) return false;
if(!col[u] && !dfs(u, 3 - color, cur)) return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
while(cin >> n >> m && n && m){
build();
for(int i = 0; i < m; i ++){
int u, v;
cin >> u >> v;
has[u][v] = has[v][u] = true;
}
for(int i = 1; i < n; i ++){
for(int j = i + 1; j <= n; j ++)
if(!has[i][j]) addEdge(i, j), addEdge(j, i);
}
for(int i = 1; i <= n; i ++){
if(!dfn[i]) root = i, tarjan(i);
}
for(int i = 1; i <= tot; i ++){
for(int j = 0; j < dcc[i].size(); j ++){
c[dcc[i][j]] = i, col[dcc[i][j]] = 0;
}
if(!dfs(dcc[i][0], 1, i)){
for(int j = 0; j < dcc[i].size(); j ++){
able[dcc[i][j]] = true;
}
}
}
int ans = 0;
for(int i = 1; i <= n; i ++){
if(!able[i]) ans ++;
}
printf("%d
", ans);
}
return 0;
}