BZOJ 1006: [HNOI2008]神奇的国度

Description

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

Input

第一行两个整数N,M。1<=N<=10000,1<=M<=1000000.表示有N个人,M对认识关系. 接下来M行每行输入一对朋友

Output

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

Sample Input

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

#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);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据