BZOJ1006【HNOI2008】神奇的国度 <弦图+MCS>

Problem

【HNOI2008】神奇的国度

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

$K$国是一个热衷三角形的国度，连人的交往也只喜欢三角原则。他们认为三角关系：即$A,B$相互认识，$B,C$相互认识，$C,A$相互认识，是简洁高效的。
为了巩固三角关系，$K$国禁止四边关系，五边关系等等的存在。所谓$N$边关系，是指$N$个人$A_1,A_2\cdots A_n$之间仅存在$N$对认识关系：$(A_1,A_2)(A_2,A_3)\cdots(A_n,A_1)$，而没有其它认识关系。比如四边关系指$A,B,C,D$四个人 $(A,B)$，$(B,C)$，$(C,D)$，$(D,A)$相互认识，而$(A,C)$，$(B,D)$不认识。
全民比赛时，为了防止做弊，规定任意一对相互认识的人不得在一队。国王想知道，最少可以分多少支队。

Input

第一行两个整数$N,M$。表示有$N$个人，$M$对认识关系。
接下来$M$行每行输入一对朋友。

Output

输出一个整数，最少可以分多少队。

Sample Input

4 5
1 2
1 4
2 4
2 3
3 4

Sample Output

3

HINT

$1\le N\le10^4,\;1\le M\le10^6$

标签：弦图 MCS

Solution

弦图与$\mathrm{MCS}$算法参见$\mathrm{CDQ}$讲义。

结论：按照任意完美消除序列倒叙染色，每次贪心染能染的最小颜色，可以使颜色数最少。

套上$\mathrm{MCS}$然后模拟染色即可，复杂度$\mathrm{O(n+m)}$。

Code

#include <bits/stdc++.h>
#define MAX_N 10000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, d[MAX_N+5], c[MAX_N+5], seq[MAX_N+5];
vector <int> G[MAX_N+5]; list <int> buk[MAX_N+5]; bool mrk[MAX_N+5];
void addedge(int u, int v) {G[u].push_back(v), G[v].push_back(u);}
void MCS() {
    memset(mrk, false, sizeof mrk);
    for (int i = 1; i <= n; i++) buk[0].push_back(i);
    for (int i = 0, mx = 0, u; i < n; seq[++i] = u, mrk[u] = true) {
        while (!buk[mx+1].empty()) mx++;
        for (u = -1; u == -1; mx--) {
            while (!buk[mx].empty() && mrk[buk[mx].front()])
                buk[mx].pop_front();
            if (!buk[mx].empty()) u = buk[mx].front();
        }
        for (int j = 0, v; j < (int)G[u].size(); j++) if (!mrk[G[u][j]])
            d[v = G[u][j]]++, buk[d[v]].push_back(v);
    }
}
int Color() {
    int ret = 0;
    memset(mrk, false, sizeof mrk);
    for (int i = 1, u = seq[1]; i <= n; u = seq[++i]) {
        for (int j = 0; j < (int)G[u].size(); j++)
            mrk[c[G[u][j]]] = true;
        for (int j = 1; !c[u]; j++) if (!mrk[j]) c[u] = j;
        for (int j = 0; j < (int)G[u].size(); j++)
            mrk[c[G[u][j]]] = false;
        ret = max(ret, c[u]);
    }
    return ret;
}
int main() {
    read(n), read(m);
    for (int i = 1, u, v; i <= m; i++)
        read(u), read(v), addedge(u, v);
    return MCS(), printf("%d\n", Color()), 0;
}