bzoj 1006

[HNOI2008]神奇的国度

Description

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

Input

第一行两个整数 $N, M(1 \le N \le 10000, 1 \le M \le 1000000)$ 表示有 $N$ 个人， $M$ 对认识关系. 接下来 $M$ 行每行输入一对朋友.

Output

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

Sample Input

Sample Output

题解

根据题目的意思，题目给出的图是一个弦图. 求弦图的最小染色数，只需要按照其完美消除序列倒序贪心的染色即可(On the coloration of perfect graphs).

这里使用最大势法求完美消除序列.

代码

#include <cassert>
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;
typedef vector<int> vi;
typedef vi::iterator vii;
#define pb push_back
#define MAXN 10100
#define MAXM 1000100

int n;
vi g[MAXN];
int ans;

struct node_t
{
    int v;
    node_t *nxt;
}node[MAXM << 2];
int used;
node_t *new_node(void)
{
    return node + (used ++);
}

node_t *f[MAXN];  /* head */
void lkto(int pos, int item)
{
    node_t *t = new_node();
    t->v = item; t->nxt = f[pos];
    f[pos] = t;
}

int usedby[MAXN];
int color[MAXN];
bitset<MAXN> added;
int label[MAXN], max_label;
void mcs(void)
{
    for (int i = 1; i <= n; i++) lkto(0, i);
    for (int i = n; i > 0; i--)
    {
        node_t *cur = f[max_label];
        assert(cur != NULL);
        while (added.test(cur->v))    /* already added */
        {
            cur = cur->nxt;
            while (NULL == cur)
                cur = f[ --max_label ];
        }
        f[ max_label ] = cur->nxt;
        while (max_label && NULL == f[max_label]) max_label--;
        int u = cur->v;
        added.set(u);
        /* the i-th is u */
        for (vii it = g[u].begin(); it != g[u].end(); it++)
        {
            int v = *it;
            if (!added.test(v))
            {
                label[v] ++;
                max_label = max(max_label, label[v]);
                lkto(label[v], v);
            }

            usedby[color[v]] = i;
        }
        for (int j = 1; j <= n; j++)
            if (usedby[j] != i)
            {
                color[u] = j;
                break;
            }
        ans = max(ans, color[u]);
    }
}

int main(void)
{
    int m;
    scanf("%d%d", &n, &m);
    while (m--)
    {
        int ai, bi;
        scanf("%d%d", &ai, &bi);
        g[ai].pb(bi); g[bi].pb(ai);
    }
    mcs();
    printf("%d\n", ans);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

# bzoj 1006

# [HNOI2008]神奇的国度

# Description

# Input

# Output

# Sample Input

# Sample Output

# 题解

# 代码