1006: [HNOI2008]神奇的国度

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 1467  Solved: 603
[Submit][Status]

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

一句话题意:题意讲的有点蛋疼,这里解释一下

为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系:这句话是说给你的图中任意一个长度大于3的环上必有一条边连接环上不相邻的两个

点(弦),这样的图叫做弦图

全民比赛时,为了防止做弊,规定任意一对相互认识的人不得在一队,国王相知道,最少可以分多少支队。:这句话其实让你把这个弦图的点染色,使得相邻的颜色不同,且总颜色个数最少

分析:裸的弦图的染色问题:先找完美消除序列,然后把序列倒过来一个点一个点贪心染色(染当前能染的最小颜色)

code:完美消除序列的时候可以用堆找最大……这个省选前在用堆写一遍吧,顺带复习……

 #include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=;
int f[maxn+],col[maxn+],label[maxn+],q[maxn+],p[maxn+];
vector<int> g[maxn+];
void ins(int x,int y)
{
g[x].push_back(y);return ;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i) g[i].clear();
for(int i=;i<m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
memset(q,,sizeof(q));
memset(label,,sizeof(label));
memset(p,,sizeof(p));
for(int i=n;i>;--i)
{
int m=,k=;
for(int i=;i<=n;++i) if(label[i]>m&&p[i]==) m=label[i],k=i;
p[k]=,q[i]=k;
for(int i=;i<g[k].size();++i) ++label[g[k][i]];
}
memset(col,,sizeof(col));
memset(f,,sizeof(f));
int ans=;
for(int k=n;k>;--k)
{
for(int i=;i<g[q[k]].size();++i) f[col[g[q[k]][i]]]=k;
int j;
for(j=;j<=n;++j) if(f[j]!=k) break;
col[q[k]]=j;
ans=max(ans,j);
}
printf("%d",ans);
return ;
}
05-08 08:41