P1330 封锁阳光大学

    • 3.3K通过
    • 9.6K提交
  • 题目提供者 yeszy 管理员
  • 评测方式 云端评测
  • 标签 图论 广度优先搜索,BFS 搜索 深度优先搜索,DFS 福建省历届夏令营
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    曹是一只爱刷街的老曹,暑假期间,他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹,感到不爽。河蟹决定封锁阳光大学,不让曹刷街。

    阳光大学的校园是一张由N个点构成的无向图,N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁,当某个点被封锁后,与这个点相连的道路就被封锁了,曹就无法在与这些道路上刷街了。非常悲剧的一点是,河蟹是一种不和谐的生物,当两只河蟹封锁了相邻的两个点时,他们会发生冲突。

    询问:最少需要多少只河蟹,可以封锁所有道路并且不发生冲突。

    输入输出格式

    输入格式:

    第一行:两个整数N,M

    接下来M行:每行两个整数A,B,表示点A到点B之间有道路相连。

    输出格式:

    仅一行:如果河蟹无法封锁所有道路,则输出“Impossible”,否则输出一个整数,表示最少需要多少只河蟹。

    输入输出样例

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

    说明

    【数据规模】

    1<=N<=10000,1<=M<=100000,任意两点之间最多有一条道路。

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