Asm.DefK国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。
| 题目名称 | 1830. [HNOI 2008]神奇的国度 |
|---|---|
| 输入输出 | bzoj_1006.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Asm.Def
于2014-11-30加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：38， 提交：114， 通过率：33.33% | ||||
 dzyo |
100 | 0.130 s | 0.85 MiB | C++ |
 sssSSSay |
100 | 0.342 s | 41.58 MiB | C++ |
|
sssSSSay |
100 | 0.351 s | 42.53 MiB | C++ |
 _rqy |
100 | 0.353 s | 24.56 MiB | C++ |
 doriko |
100 | 0.367 s | 38.79 MiB | C++ |
 叶寒孤舟 |
100 | 0.369 s | 17.22 MiB | C++ |
 HeHe |
100 | 0.384 s | 0.80 MiB | C++ |
 苦读依旧 |
100 | 0.390 s | 50.87 MiB | C++ |
|
苦读依旧 |
100 | 0.397 s | 62.32 MiB | C++ |
 J_william |
100 | 0.414 s | 30.94 MiB | C++ |
| 关于 神奇的国度 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
图论神题……不过贪心的思路很简单，每次选择一个未染色的点，满足它在未染色的点中已染色邻接点个数最多，用一个可用的最小的颜色对它染色后加入已染色集合。
证明详见WC2009讲稿 弦图与区间图-CDQ 这题最快可以用桶优化到$O(n+m)$，不过n只有10000，直接暴力$O(n^2 + m)$可过 | ||||
【题目描述】
【输入格式】
第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系. 接下来M行每行输入一对朋友
【输出格式】
输出一个整数，最少可以分多少队
【样例输入】
4 5 1 2 1 4 2 4 2 3 3 4
【样例输出】
3
【提示】
一种方案(1,3)(2)(4)