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

相关文章

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

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

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

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

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》:本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理?proxy

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

C/C++随机数生成的五种方法

《C/C++随机数生成的五种方法》C++作为一种古老的编程语言,其随机数生成的方法已经经历了多次的变革,早期的C++版本使用的是rand()函数和RAND_MAX常量,这种方法虽然简单,但并不总是提供... 目录C/C++ 随机数生成方法1. 使用 rand() 和 srand()2. 使用 <random

Flask 验证码自动生成的实现示例

《Flask验证码自动生成的实现示例》本文主要介绍了Flask验证码自动生成的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习... 目录生成图片以及结果处理验证码蓝图html页面展示想必验证码大家都有所了解,但是可以自己定义图片验证码