Description
K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2…An之间仅存在N对认识关系:(A1A2)(A2A3)…(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。
第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系. 接下来M行每行输入一对朋友
Output
输出一个整数，最少可以分多少队
4 5
1 2
1 4
2 4
2 3
3 4
Sample Output
3
HINT
一种方案(1,3)(2)(4)
Source
Solution
WIKI PEDIA
弦图与区间图-陈丹琦
弦(chord)：连接环中不相邻的两个点的边。
弦图(chordalgraph)：一个无向图称为弦图当且仅当图中任意长度大于3的环都至少有一个弦。
单纯点(simplicialvertex)：设N(v)表示与点v相邻的点集。一个点称为单纯点当{v} + N(v)的诱导子图为一个团。
完美消除序列(perfect elimination ordering)：这是一个序列{v[i]}，它满足v[i]在{v[i..n]}的诱导子图中为单纯点。
弦图的判定：存在完美消除序列的图为弦图。可以用MCS最大势算法求出完美消除序列。
最大势算法 Maximum Cardinality Search
从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。
设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。
用n个vector来保存label为i的是哪些点，可以使复杂度达到O(n+m)。
弦图上的问题：
用最少的颜色给每个点染色使得相邻的点染的颜色不同：完美消除序列从后往前依次给每个点染上可以染的最小的颜色。
最大独立集：完美消除序列从前往后能选就选。
判断一个序列是否为完美消除序列：设{vi+1,…,vn}中所有与vi相邻的点依次为vj1,…, vjk。只需判断vj1是否与vj2,…, vjk相邻即可。
区间图(Interval Graph)：给定一些区间，定义一个相交图为每个顶点表示一个区间，两个点有边当且仅当两个区间的交集非空。
区间图一定是弦图。
给定n个区间，所对应的区间图为G
G的一个完美消除序列：将所有的区间按照右端点从小到大排序。
PS：弦图是个神奇的东西QAQ，先对他进行MCS 求出完美消除序列 然后完美消除序列倒序来染色，每个点染成能染的最小值就好了。
有线性做法，然而不会，于是写了个log的。。。
Code
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
| #include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1000005;
bool vis[maxn];
int n, m, x, y, tmp, now, cnte, ans, h[maxn], lab[maxn], pe[maxn], col[maxn], dst[maxn];
priority_queue<pair<int, int> > Q;
struct edge_t { int to, next; } edge[maxn << 1];
void ins(int x, int y) {
edge[++cnte].to = y;
edge[cnte].next = h[x];
h[x] = cnte;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < m; ++i) {
scanf("%d %d", &x, &y);
ins(x, y); ins(y, x);
}
tmp = n;
for (int i = 1; i <= n; ++i) Q.push(make_pair(lab[i] = 0, i));
while (!Q.empty()) {
now = Q.top().second; Q.pop();
if (vis[now]) continue;
vis[now] = true;
pe[tmp--] = now;
int v;
for (int i = h[now]; i; i = edge[i].next) {
if (vis[v = edge[i].to]) continue;
++lab[v];
Q.push(make_pair(lab[v], v));
}
}
for (int i = n; i >= 1; --i) {
tmp = 0;
for (int j = h[pe[i]]; j; j = edge[j].next)
if (col[edge[j].to]) dst[tmp++] = col[edge[j].to];
sort(dst, dst + tmp);
int ptr = 0;
for (col[pe[i]] = 1; ; ++col[pe[i]]) {
while (ptr < tmp && dst[ptr] < col[pe[i]]) ++ptr;
if (ptr == tmp || col[pe[i]] < dst[ptr]) break;
}
ans = max(ans, col[pe[i]]);
}
printf("%d", ans);
}
|