P3524 [POI2011]IMP-Party

    • 131通过
    • 277提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 字符串 POI 2011 Special Judge 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms-5000ms / 64MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Byteasar intends to throw up a party.

    Naturally, he would like it to be a success. Furthermore, Byteasar is quite certain that to make it so it suffices if all invited guests know each other. He is currently trying to come up with a list of his friends he would like to invite.

    Byteasar has $n$ friends, where $n$ is divisible by 3.

    Fortunately, most of Byteasar's friends know one another.

    Furthermore, Byteasar recalls that he once attended a party where there were $\frac{2}{3}n$ of his friends, and where everyone knew everyone else.

    Unfortunately, Byteasar does not quite remember anything else from that party.

    In particular, he has no idea which of his friends attended it.

    Byteasar does not feel obliged to throw a huge party, but he would like to invite at least \frac{n}{3} of his friends.

    He has no idea how to choose them, so he asks you for help.

    给定一张n个点m条边的图$n\equiv 0(mod\ 3)$,保证存在一个大小为$\frac{2}{3}n$的团,要求输出一个大小为$\frac{n}{3}$的团

    输入输出格式

    输入格式:

    In the first line of the standard input two integers, $n$ and $m$ ($3\le n\le 3\ 000$, $\frac{\frac{2}{3}n(\frac{2}{3}n-1)}{2}\leq m\leq \frac{n(n-1)}{2}$), are given,separated by a single space. These denote the number of Byteasar's friends and the number of pairs of his friends who know each other, respectively.

    Byteasar's friends are numbered from 1 to $n$.

    Each of the following $m$ lines holds two integers separated by a single space.

    The numbers in line no. $i+1$ (for $i=1,2,...,m$) are $a_i$ and $b_i$($1\le a_i<b_i\le n$), separated by a single space, which denote that the persons $a_i$ and $b_i$ know each other. Every pair of numbers appears at most once on the input.

    输出格式:

    In the first and only line of the standard output your program should print $\frac{n}{3}$ numbers, separated by single spaces, in increasing order. These number should specify the numbers of Byteasar's friends whom he should invite to the party. As there are multiple solutions, pick one arbitrarily.

    输入输出样例

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

    说明

    给定一张n个点m条边的图$n\equiv 0(mod\ 3)$,保证存在一个大小为$\frac{2}{3}n$的团,要求输出一个大小为$\frac{n}{3}$的团

    样例图:

    由@zhouyonglong提供SPJ

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