| 题目名称 | 4147. 寿司NPC2 |
|---|---|
| 输入输出 | NPCII.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 flyfree
于2025-05-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：9， 通过率：22.22% | ||||
 flyfree |
100 | 0.027 s | 3.29 MiB | C++ |
|
darkMoon |
100 | 0.029 s | 3.65 MiB | C++ |
|
flyfree |
50 | 0.031 s | 3.67 MiB | C++ |
|
flyfree |
0 | 1.439 s | 3.29 MiB | C++ |
|
flyfree |
0 | 1.555 s | 3.31 MiB | C++ |
|
flyfree |
0 | 1.559 s | 3.29 MiB | C++ |
|
darkMoon |
0 | 3.009 s | 259.50 MiB | C++ |
|
darkMoon |
0 | 5.715 s | 515.29 MiB | C++ |
|
darkMoon |
0 | 12.874 s | 259.33 MiB | C++ |
| 关于 寿司NPC2 的近10条评论(全部评论) |
|---|
【题目背景】
你已经手撕掉一个 NPC 了，接下来挑战下一个吧 (
【题目描述】
给定一个 n 个点 m 条边的无向图，输出这个图的点团个数
团的定义为任意两个点都相邻的子图
【输入格式】
第一行两个数 n,m
接下来 m 行每行两个整数 x y 表示一个从 x 连向 y 的边，不保证图连通，保证不存在自环。
【输出格式】
一行一个整数表示点独立集个数
【样例输入】
3 2 1 2 2 3
【样例输出】
6
【样例说明】
团分别为 {1},{2},{3},{1 2},{2 3},{0}。
【数据规模与约定】
对于 40% 的数据 n <= 20
对于另外 60% 的数据 n <= 50
对于 100% 的数据，满足 m <= 2n。
【来源】
集训队论文：浅谈信息学竞赛中的独立集问题