POJ 2942 Knights of the Round Table

Description

有N个骑士和M对憎恨关系，开会必须满足以下要求

1：互相憎恨不能坐在相邻位置

2：奇数个骑士

现要求出有几个骑士不能参加任何可能的会议

Solution

将没有憎恨关系的两个骑士连无向边，求出每个可能在奇数环中的骑士，剩下的就是不能参加任何会议的骑士

有两个引理

1：不同点双联通分量中的点，不可能在同一个环内—— 因为存在割点或者不连通

2：若在点双联通分量内存在奇数环，那么该双联通分量内的点都可以在一个奇数环内——脑胡一下233

然后我们求出点双联通分量，并在分量内染色找奇数环，若找到奇数环，就标记这个双联通分量内的每个点。

Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<vector>
  5 #define rd read()
  6 #define rep(i,a,b) for(int i = (a); i <= (b); ++i)
  7 #define per(i,a,b) for(int i = (a); i >= (b); --i)
  8 #define cl(a) memset(a, 0, sizeof(a));
  9 using namespace std;
 10 
 11 const int N = 3e3 + 5, M = 1e6 + 1e4;
 12 
 13 int head[N], tot;
 14 int cut[N], cnt, blo, col[N], ok[N], mp[N][N], in[N], n, m, dfn[N], low[N];
 15 int st[N], tp, rt;
 16 
 17 vector<int> q;
 18 
 19 struct edge {
 20     int nxt, to;
 21 }e[M << 2];
 22 
 23 int read() {
 24     int X = 0, p = 1; char c = getchar();
 25     for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p =-1;
 26     for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';
 27     return X * p;
 28 }
 29 
 30 void add(int u, int v) {
 31     e[++tot].to = v;
 32     e[tot].nxt = head[u];
 33     head[u] = tot;
 34 }
 35 
 36 int dfs(int u, int now) {
 37     col[u] = now;
 38     for(int i = head[u]; i; i = e[i].nxt) {
 39         int nt = e[i].to;
 40         if(in[nt] != blo) continue;
 41         if(!col[nt]) {
 42             if(dfs(nt, 3 - now)) return 1;
 43         }
 44         else if(col[nt] + now != 3) return 1;
 45     }
 46     return 0;
 47 }
 48 
 49 void tarjan(int u) {
 50     dfn[u] = low[u] = ++cnt;
 51     st[++tp] = u;
 52     int flag = 0;
 53     for(int i = head[u]; i; i = e[i].nxt) {
 54         int nt = e[i].to;
 55         if(!dfn[nt]) {
 56             tarjan(nt);
 57             low[u] = min(low[u], low[nt]);
 58             if(low[nt] >= dfn[u]) {
 59                 ++flag;    ++blo;
 60                 q.clear();
 61                 if(flag > 1 || u != rt) cut[u] = 1;
 62                 for(int z;;) {
 63                     z = st[tp--];
 64                     q.push_back(z);
 65                     in[z] = blo;
 66                     if(z == nt) break;
 67                 }
 68                 q.push_back(u);
 69                 in[u] = blo;
 70                 cl(col);
 71                 if(dfs(u, 1)) 
 72                     for(int i = 0, len = q.size(); i < len; ++i) ok[q[i]] = 1;
 73             }
 74         } else low[u] = min(low[u], dfn[nt]);
 75     }
 76 }
 77 
 78 void work() {
 79     rep(i, 1, m) {
 80         int u = rd, v = rd;
 81         mp[u][v] = mp[v][u] = 1;
 82     }
 83     rep(i, 1, n) rep(j, 1, n) 
 84         if(i != j && !mp[i][j]) add(i, j);
 85     rep(i, 1, n) 
 86         if(!dfn[i]) tarjan(rt = i);
 87     int ans = 0;
 88     rep(i, 1, n) if(!ok[i]) ans++;
 89     printf("%d
", ans);
 90 }
 91 
 92 int main()
 93 {
 94     for(; ;) {
 95         n = rd; m = rd;
 96         if(!n && !m) return 0;
 97         cl(head);
 98         cl(cut); cl(col);
 99         cl(dfn); cl(low);
100         cl(ok); cl(mp);
101         cl(in);
102         tot = cnt = blo = 0;
103         work();
104     }
105 }

View Code