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

相关文章

快速修复一个Panic的Linux内核的技巧

《快速修复一个Panic的Linux内核的技巧》Linux系统中运行了不当的mkinitcpio操作导致内核文件不能正常工作,重启的时候,内核启动中止于Panic状态,该怎么解决这个问题呢?下面我们就... 感谢China编程(www.chinasem.cn)网友 鸢一雨音 的投稿写这篇文章是有原因的。为了配置完

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》:本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》:本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

Java利用docx4j+Freemarker生成word文档

《Java利用docx4j+Freemarker生成word文档》这篇文章主要为大家详细介绍了Java如何利用docx4j+Freemarker生成word文档,文中的示例代码讲解详细,感兴趣的小伙伴... 目录技术方案maven依赖创建模板文件实现代码技术方案Java 1.8 + docx4j + Fr

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.