P3196 [HNOI2008]神奇的国度

    • 241通过
    • 600提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 NP问题 哈希,HASH 广度优先搜索,BFS 2008 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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行每行输入一对朋友

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    4 5
    1 2
    1 4
    2 4
    2 3
    3 4
    输出样例#1: 复制
    3

    说明

    一种方案(1,3)(2)(4)

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。