必威体育Betway必威体育官网
当前位置:首页 > IT技术

割点详解

时间:2019-10-12 17:14:36来源:IT技术作者:seo实验室小编阅读:74次「手机版」
 

定义:

在一个无向图中,如果去掉一个点和它所连出去的的所有边,使得剩下的点不联通(即分成一个以上的强连通分量)时,这个点被称为关节点。

题目:

来看一道裸题:有n(1≤n≤10^6)个点,m(1≤m≤5*10^6)条边,现在让你求图中所有的关节点。

思路1:

枚举+dfs

枚举割掉那些点,再跑深搜看看剩下的点是否连通即可。

时间复杂度:O(n(n+m))

代码就不贴了(人人都会打)。

思路2:

割点模板(类似于强连通模板)。

我们想,对于一棵树来说,想让根节点成为关节点,他至少有两个儿子。

如图1,当根节点只有一个儿子时,割掉它,剩下的点必然联通,且新的树的个节点为它的儿子;

如图2,当根节点有两个儿子时,割掉它,剩下的点必然不联通(有两个强连通分量)。

那么对于非根节点呢?

来看一个性质:在无向图G中,刚且仅当点u存在一个可遍历到的后代v,且点v无法走回点u的前辈时,点u就为割点。

这很容易证。

如图3,点v1,v2均为点u的儿子,我们可以发现(手动模拟,v1和v2不联通),点u为割点。

此时点u存在一个可遍历到的后代v1,且点v1无法走回点u的前辈,满足该性质。

我们在v1,v2间加上一条边。

如图4,此时我们可以发现点u并不为割点(此时v1,v2和点u的前辈联通)。

此时点u存在一个可遍历到的后代v1,且点v1,v2都可以走回点u的前辈,不满足该性质。

我们能想到什么?

详见代码。

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define _ 200010
using namespace std;
	struct node{int x,y,next;} a[_];
	int n,m,len=0,id=0,ans=0;
	int last[_],low[_],dfn[_];
/*dfn[i]表示点i被访问的时间戳 
low[i]表示点i及i的子树中所有结点能到达的结点中dfn最小的结点的时间戳*/ 
	bool bz[_];
void ins(int x,int y)
{
	a[++len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;
}
void dfs(int x,int root)
//x表示当前访问到第x个点,root表示已root为根节点的子树的根 
{
	int tot=0;
	low[x]=dfn[x]=++id;
//记录时间戳 
	for(int i=last[x];i;i=a[i].next)
	{
		int y=a[i].y;
		if(!dfn[y])
		{
			dfs(y,root);
			low[x]=min(low[x],low[y]);
//更新当前节点的low值 
			if(low[y]>=dfn[x]&&x!=root) bz[x]=true;
/*非根且子树能达到的dfn最小的结点的时间>=自己的时间时,
说明它的子树中最早能访问到的结点都比它后访问,此时只要不为根就一定是割点*/ 
			if(x==root) tot++;
//更新入度 
		}
		low[x]=min(low[x],dfn[y]);
//把点x及x的子树可以达到的dfn的最小结点更新
	}
	if(x==root&&tot>=2) bz[root]=true;
//如果一个点为根且入度>=2,则一定为割点,因为一棵树的根一删不那么它的子树一定不连通了
}
int main()
{
	int x,y,t;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		ins(x,y);
		ins(y,x);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) dfs(i,i);
	for(int i=1;i<=n;i++)
		if(bz[i]) ans++;
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)
		if(bz[i]) printf("%d ",i);
}

相关阅读

spring定时任务详解(@Scheduled注解)

文章出处:http://blog.csdn.net/qq_33556185/article/details/51852537在springMVC里使用spring的定时任务非常的简单,如下:(一)在xml

科普:四大微信第三方平台微店、微盟、有赞、点点客的区

一、微店&ldquo;微店&rdquo;几乎已经成为一个行业词了,最早的微店产品是口袋购物旗下的&ldquo;微店&rdquo;。上线于2014年初的微店

StartActivityForResult详解

转载自:https://www.cnblogs.com/zgqys1980/p/5286208.html 一、如果想在Activity中得到新打开Activity 关闭后返回的数据,需要使

C# 中的委托和事件(详解:简单易懂的讲解)

本文转载自 http://www.cnblogs.com/SkySoot/archive/2012/04/05/2433639.html C# 中的委托和事件(详解) https://www.cnblogs.c

【原创】无线破解Aircrack-ng套件详解--airmon-ng与airo

一:Aircrack-ng详解   1.1 Aircrack-ng概述 Aircrack-ng是一款用于破解无线802.11WEP及WPA-PSK加密的工具,该工具在2005年11月之

分享到:

栏目导航

推荐阅读

热门阅读