热门标签 | 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树


推荐阅读
  • 如果应用程序经常播放密集、急促而又短暂的音效(如游戏音效)那么使用MediaPlayer显得有些不太适合了。因为MediaPlayer存在如下缺点:1)延时时间较长,且资源占用率高 ... [详细]
  • malloc 是 C 语言中的一个标准库函数,全称为 memory allocation,即动态内存分配。它用于在程序运行时申请一块指定大小的连续内存区域,并返回该区域的起始地址。当无法预先确定内存的具体位置时,可以通过 malloc 动态分配内存。 ... [详细]
  • 本文详细介绍了Linux系统中用于管理IPC(Inter-Process Communication)资源的两个重要命令:ipcs和ipcrm。通过这些命令,用户可以查看和删除系统中的消息队列、共享内存和信号量。 ... [详细]
  • NX二次开发:UFUN点收集器UF_UI_select_point_collection详解
    本文介绍了如何在NX中使用UFUN库进行点收集器的二次开发,包括必要的头文件包含、初始化和选择点集合的具体实现。 ... [详细]
  • 本文介绍了如何在 ASP.NET 中设置 Excel 单元格格式为文本,获取多个单元格区域并作为表头,以及进行单元格合并、赋值、格式设置等操作。 ... [详细]
  • [c++基础]STL
    cppfig15_10.cppincludeincludeusingnamespacestd;templatevoidprintVector(constvector&integer ... [详细]
  • 蒜头君的倒水问题(矩阵快速幂优化)
    蒜头君将两杯热水分别倒入两个杯子中,每杯水的初始量分别为a毫升和b毫升。为了使水冷却,蒜头君采用了一种特殊的方式,即每次将第一杯中的x%的水倒入第二杯,同时将第二杯中的y%的水倒入第一杯。这种操作会重复进行k次,最终求出两杯水中各自的水量。 ... [详细]
  • Python多线程详解与示例
    本文介绍了Python中的多线程编程,包括僵尸进程和孤儿进程的概念,并提供了具体的代码示例。同时,详细解释了0号进程和1号进程在系统中的作用。 ... [详细]
  • 本文将介绍如何在混合开发(Hybrid)应用中实现Native与HTML5的交互,包括基本概念、学习目标以及具体的实现步骤。 ... [详细]
  • MySQL初级篇——字符串、日期时间、流程控制函数的相关应用
    文章目录:1.字符串函数2.日期时间函数2.1获取日期时间2.2日期与时间戳的转换2.3获取年月日、时分秒、星期数、天数等函数2.4时间和秒钟的转换2. ... [详细]
  • 解决SQL Server数据库sa登录名无法连接的问题
    在安装SQL Server数据库后,使用Windows身份验证成功,但使用SQL Server身份验证时遇到问题。本文将介绍如何通过设置sa登录名的密码、启用登录名状态以及开启TCP协议来解决这一问题。 ... [详细]
  • LDAP服务器配置与管理
    本文介绍如何通过安装和配置SSSD服务来统一管理用户账户信息,并实现其他系统的登录调用。通过图形化交互界面配置LDAP服务器,确保用户账户信息的集中管理和安全访问。 ... [详细]
  • php更新数据库字段的函数是,php更新数据库字段的函数是 ... [详细]
  • 自然语言处理(NLP)——LDA模型:对电商购物评论进行情感分析
    目录一、2020数学建模美赛C题简介需求评价内容提供数据二、解题思路三、LDA简介四、代码实现1.数据预处理1.1剔除无用信息1.1.1剔除掉不需要的列1.1.2找出无效评论并剔除 ... [详细]
  • 思科IOS XE与ISE集成实现TACACS认证配置
    本文详细介绍了如何在思科IOS XE设备上配置TACACS认证,并通过ISE(Identity Services Engine)进行用户管理和授权。配置包括网络拓扑、设备设置和ISE端的具体步骤。 ... [详细]
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社区 版权所有