IndiaHacks 2016 - Online Edition (Div. 1 + Div. 2) E. Bear and Forgotten Tree 2 bfs set 反图的生成树 快速连通块

本文主要是介绍IndiaHacks 2016 - Online Edition (Div. 1 + Div. 2) E. Bear and Forgotten Tree 2 bfs set 反图的生成树 快速连通块,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

老规矩,抄一波QSC,自己的写在后面

 

E. Bear and Forgotten Tree 2

题目连接:

http://www.codeforces.com/contest/653/problem/E

Description

A tree is a connected undirected graph consisting of n vertices and n  -  1 edges. Vertices are numbered 1 through n.

Limak is a little polar bear. He once had a tree with n vertices but he lost it. He still remembers something about the lost tree though.

You are given m pairs of vertices (a1, b1), (a2, b2), ..., (am, bm). Limak remembers that for each i there was no edge between ai and bi. He also remembers that vertex 1 was incident to exactly k edges (its degree was equal to k).

Is it possible that Limak remembers everything correctly? Check whether there exists a tree satisfying the given conditions

Input

The first line of the input contains three integers n, m and k () — the number of vertices in Limak's tree, the number of forbidden pairs of vertices, and the degree of vertex 1, respectively.

The i-th of next m lines contains two distinct integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the i-th pair that is forbidden. It's guaranteed that each pair of vertices will appear at most once in the input.

Output

Print "possible" (without quotes) if there exists at least one tree satisfying the given conditions. Otherwise, print "impossible" (without quotes).

Sample Input

5 4 2
1 2
2 3
4 2
4 1

Sample Output

possible

Hint

题意

给你n个点,然后给你m个限制,每个限制说ai,bi之间不能连边。

问你能否构造出一棵生成树,且1号点的度数恰好等于k

题解:

首先忽略掉恰好等于k这个条件,实际上就是判断这个图是否连通就好了。

然后我们看看1号点的反图的度数是否大于等于k,小于k肯定不行。

然后我们把1号点去掉,跑bfs/dfs,看有多少个连通块和1号点能够相连,如果有大于k个连通块,肯定也是不行的。

小于等于k个连通块就可以。

然后现在问题是那个bfs和dfs跑连通块复杂度可能是n^2的,你遍历边的时候,会遍历到无意义的点。

所以我们需要用一个set去维护现在有哪些点还没有访问。

总之,就是你需要实现一个类似lowbit的功能,然后就可以优化你的dfs/bfs。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
int n,m,k;
set<int>vis,E[maxn];
int q[maxn],st;
void solve(int x)
{vis.erase(x);q[st++]=x;for(int i=0;i<st;i++){int now = q[i];int pre = 1;while(1){auto next = vis.upper_bound(pre);if(next==vis.end())break;int v = *next;pre = v;if(E[now].count(v))continue;q[st++]=v;vis.erase(v);}}
}
int main()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);E[x].insert(y);E[y].insert(x);}if(k>n-1-E[1].size())return puts("impossible"),0;for(int i=2;i<=n;i++)vis.insert(i);int cnt=0;for(int i=2;i<=n;i++){if(vis.count(i)){cnt++;st=0;solve(i);int flag = 0;for(int j=0;j<st;j++)if(!E[1].count(q[j]))flag=1;if(flag==0)return puts("impossible"),0;}}if(cnt>k)return puts("impossible"),0;return puts("possible"),0;
}

这个题目set的作用是记录未访问的点。set其实模拟的是一个链表。bfs中访问过的点就从set中移掉了。而且无后效性。

为什么不用vis?用set更快。。可以跳过中间的点。。可能用链表会更快一点吧?

 

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
int n,m,k;
set<int>vis,E[maxn];
int q[maxn],st;
void solve(int x)
{vis.erase(x);q[st++]=x;for(int i=0;i<st;i++){int now = q[i];int pre = 1;for (auto it = vis.begin(); it != vis.end();){int v = *it;pre = v;if(E[now].count(v)){it++;continue;}q[st++]=v;vis.erase(it++);}}
}
int main()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);E[x].insert(y);E[y].insert(x);}if(k>n-1-E[1].size())return puts("impossible"),0;for(int i=2;i<=n;i++)vis.insert(i);int cnt=0;for(int i=2;i<=n;i++){if(vis.count(i)){cnt++;st=0;solve(i);int flag = 0;for(int j=0;j<st;j++)if(!E[1].count(q[j]))flag=1;if(flag==0)return puts("impossible"),0;}}if(cnt>k)return puts("impossible"),0;return puts("possible"),0;
}

 

这篇关于IndiaHacks 2016 - Online Edition (Div. 1 + Div. 2) E. Bear and Forgotten Tree 2 bfs set 反图的生成树 快速连通块的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1050274

相关文章

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

Linux如何快速检查服务器的硬件配置和性能指标

《Linux如何快速检查服务器的硬件配置和性能指标》在运维和开发工作中,我们经常需要快速检查Linux服务器的硬件配置和性能指标,本文将以CentOS为例,介绍如何通过命令行快速获取这些关键信息,... 目录引言一、查询CPU核心数编程(几C?)1. 使用 nproc(最简单)2. 使用 lscpu(详细信

shell中set -u、set -x、set -e的使用

《shell中set-u、set-x、set-e的使用》本文主要介绍了shell中set-u、set-x、set-e的使用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录✅ 1. set -u:防止使用未定义变量 作用: 示例:❌ 报错示例输出:✅ 推荐使用场景:✅ 2. se

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

python如何生成指定文件大小

《python如何生成指定文件大小》:本文主要介绍python如何生成指定文件大小的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python生成指定文件大小方法一(速度最快)方法二(中等速度)方法三(生成可读文本文件–较慢)方法四(使用内存映射高效生成

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin(推荐)的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

8种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

《8种快速易用的PythonMatplotlib数据可视化方法汇总(附源码)》你是否曾经面对一堆复杂的数据,却不知道如何让它们变得直观易懂?别慌,Python的Matplotlib库是你数据可视化的... 目录引言1. 折线图(Line Plot)——趋势分析2. 柱状图(Bar Chart)——对比分析3