热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【BZOJ4424】Cf19EFairyDFS树

【BZOJ4424】Cf19EFairyDescription给定n个点,m条边的无向图,可以从图中删除一条边,问删除哪些边可以使图变成一个二分图。给定n个点,m条边的无向图,可以
【BZOJ4424】Cf19E Fairy

Description

给定 n 个点,m 条边的无向图,可以从图中删除一条边,问删除哪些边可以使图变成一个二分图。

Input

第 1 行包含两个整数 n,m。分别表示点数和边数。
第 2 到 m+1 行每行两个数 x,y 表示有一条(x,y)的边。

Output

输出第一行一个整数,表示能删除的边的个数。
接下来一行按照从小到大的顺序输出边的序号。

Sample Input

4 4
1 2
1 3
2 4
3 4

Sample Output

4
1 2 3 4

HINT

100%的数据,n,m<=1000000

题解:先建出DFS树,然后每条非树边都对应一个简单环。找出所有奇环偶环及其覆盖的树边,然后分类讨论:

如果没有奇环,那么删哪条边都行。
如果只有一个奇环,那么可以删它覆盖的树边,也可以删这条非树边。
如果有多个奇环,那么必须删掉被所有奇环都覆盖的边。

但是问题来了,奇环+偶环=奇环,也就意味着如果一条边即被奇环覆盖也被偶环覆盖,那么删掉这条边是没有的,判掉就好。

#include 
#include 
#include 
using namespace std;
const int maxn=1000010;
int n,m,sum,ans,cnt;
int f[maxn],to[maxn<<1],next[maxn<<1],ont[maxn<<1],head[maxn],pa[maxn],pb[maxn],vis[maxn],dep[maxn];
int fa[20][maxn],Log[maxn],pc[maxn],s1[maxn],s0[maxn],from[maxn],ok[maxn];
int find(int x)
{
	return (f[x]==x)?x:(f[x]=find(f[x]));
}
inline void add(int a,int b)
{
	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
void dfs1(int x)
{
	vis[x]=1;
	for(int i=head[x];i!=-1;i=next[i])	if(!vis[to[i]])
		ont[i]=1,fa[0][to[i]]=x,dep[to[i]]=dep[x]+1,from[to[i]]=(i>>1)+1,dfs1(to[i]);
}
inline int lca(int a,int b)
{
	if(dep[a]=0;i--)	if(dep[fa[i][a]]>=dep[b])	a=fa[i][a];
	if(a==b)	return a;
	for(int i=Log[dep[a]];i>=0;i--)	if(fa[i][a]!=fa[i][b])	a=fa[i][a],b=fa[i][b];
	return fa[0][a];
}
void dfs2(int x)
{
	for(int i=head[x];i!=-1;i=next[i])	if(ont[i])	dfs2(to[i]),s1[x]+=s1[to[i]],s0[x]+=s0[to[i]];
}
inline int rd()
{
	int ret=0,f=1;	char gc=getchar();
	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)	f=-f;	gc=getchar();}
	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+(gc^‘0‘),gc=getchar();
	return ret*f;
}
int main()
{
	n=rd(),m=rd();
	int i,j;
	memset(head,-1,sizeof(head));
	for(i=1;i<=n;i++)	f[i]=i;
	for(i=1;i<=m;i++)
	{
		pa[i]=rd(),pb[i]=rd(),add(pa[i],pb[i]),add(pb[i],pa[i]);
		if(find(pa[i])!=find(pb[i]))	f[f[pa[i]]]=f[pb[i]];
	}
	for(i=1;i<=n;i++)	if(!vis[i])	dep[i]=1,dfs1(i);
	for(i=2;i<=n;i++)	Log[i]=Log[i>>1]+1;
	for(j=1;(1<

【BZOJ4424】Cf19E Fairy DFS树


推荐阅读
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • importjava.io.*;importjava.util.*;publicclass五子棋游戏{staticintm1;staticintn1;staticfinalintS ... [详细]
  • 本文介绍了SIP(Session Initiation Protocol,会话发起协议)的基本概念、功能、消息格式及其实现机制。SIP是一种在IP网络上用于建立、管理和终止多媒体通信会话的应用层协议。 ... [详细]
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • 本文介绍了如何通过C#语言调用动态链接库(DLL)中的函数来实现IC卡的基本操作,包括初始化设备、设置密码模式、获取设备状态等,并详细展示了将TextBox中的数据写入IC卡的具体实现方法。 ... [详细]
  • 本文详细介绍了iOS应用的生命周期,包括各个状态及其转换过程中的关键方法调用。 ... [详细]
  • 本文将从基础概念入手,详细探讨SpringMVC框架中DispatcherServlet如何通过HandlerMapping进行请求分发,以及其背后的源码实现细节。 ... [详细]
  • Windows操作系统提供了Encrypting File System (EFS)作为内置的数据加密工具,特别适用于对NTFS分区上的文件和文件夹进行加密处理。本文将详细介绍如何使用EFS加密文件夹,以及加密过程中的注意事项。 ... [详细]
  • 如何在PHP中安装Xdebug扩展
    本文介绍了如何从PECL下载并编译安装Xdebug扩展,以及如何配置PHP和PHPStorm以启用调试功能。 ... [详细]
  • 解决Visual Studio Code中PHP Intelephense误报问题
    PHP作为一种高度灵活的编程语言,其代码结构可能导致Intelephense插件在某些情况下报告不必要的错误或警告。自1.3.3版本起,Intelephense引入了多个配置选项,允许用户根据具体的工作环境和编程风格调整这些诊断信息的显示。 ... [详细]
  • 在日常生活中,支付宝已成为不可或缺的支付工具之一。本文将详细介绍如何通过支付宝实现免费提现,帮助用户更好地管理个人财务,避免不必要的手续费支出。 ... [详细]
  • 我的读书清单(持续更新)201705311.《一千零一夜》2006(四五年级)2.《中华上下五千年》2008(初一)3.《鲁滨孙漂流记》2008(初二)4.《钢铁是怎样炼成的》20 ... [详细]
  • 探索AI智能机器人自动盈利系统的构建
    用户可通过支付198元押金及30元设备维护费租赁AI智能机器人,推荐他人加入可获得相应佣金。随着推荐人数的增加,用户将逐步解锁更高版本,享受更多收益。 ... [详细]
  • 本文将详细介绍如何在二进制和十六进制之间进行准确的转换,并提供实际的代码示例来帮助理解这一过程。 ... [详细]
  • empty,isset首先都会检查变量是否存在,然后对变量值进行检测。而is_null只是直接检查变量值,是否为null,因此如果变量未定义就会出现错误!检测一个变量是否是null ... [详细]
author-avatar
恐龙
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有