专栏首页数据结构与算法P3388 【模板】割点(割顶)

P3388 【模板】割点(割顶)

题目背景

割点

题目描述

给出一个n个点,m条边的无向图,求图的割点。

输入输出格式

输入格式:

第一行输入n,m

下面m行每行输入x,y表示x到y有一条边

输出格式:

第一行输出割点个数

第二行按照节点编号从小到大输出节点,用空格隔开

输入输出样例

输入样例#1:

6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6

输出样例#1:

1 
5

说明

n,m均为100000

tarjan 图不一定联通!!!

割点真是一个非常神奇的东西。

虽然和tarjan很像,

而且能理解其中的奥秘。

但是代码还是看的一脸蒙蔽,。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 #include<stack> 
 8 #define lli long long int 
 9 using namespace std;
10 const int MAXN=1000001;
11 const int maxn=0x7fffff;
12 inline void read(int &n)
13 {
14     char c='+';int x=0;bool flag=0;
15     while(c<'0'||c>'9')
16     {c=getchar();if(c=='-')flag=1;}
17     while(c>='0'&&c<='9')
18     {x=(x<<1)+(x<<3)+c-48;c=getchar();}
19     flag==1?n=-x:n=x;
20 }
21 int n,m;
22 struct node
23 {
24     int u,v,nxt;
25 }edge[MAXN];
26 int head[MAXN];
27 int num=1;
28 void add_edge(int x,int y)
29 {
30     edge[num].u=x;
31     edge[num].v=y;
32     edge[num].nxt=head[x];
33     head[x]=num++;
34 }
35 int dfn[MAXN];//dfs的顺序
36 int low[MAXN];// 每个点能追溯到的最近公共祖先
37 int vis[MAXN];
38 int ans[MAXN];// 是否是割点 
39 int ansnum; //割点的数量 
40 int tot=0;
41 int tarjan(int now,int fa)
42 {
43     dfn[now]=low[now]=++tot;    
44     int ch=0;
45     for(int i=head[now];i!=-1;i=edge[i].nxt)
46     {
47         if(low[edge[i].v]!=0)
48             low[edge[i].u]=min(low[edge[i].u],dfn[edge[i].v]);
49         else 
50         if(low[edge[i].v]==0)
51         {
52             ch++;//孩子的数量
53             int nxt=tarjan(edge[i].v,edge[i].u);
54             low[edge[i].u]=min(low[edge[i].u],low[edge[i].v]);
55             if((fa==-1&&ch>1)||(fa!=-1&&dfn[edge[i].u]==low[edge[i].v]))
56             {
57                 if(!ans[edge[i].u])
58                 {
59                     ans[edge[i].u]=1;
60                     ansnum++;
61                 }
62             }
63         }
64     }
65     return low[now];
66 }
67 int main()
68 {
69     read(n);read(m);
70     memset(head,-1,sizeof(head));
71     for(int i=1;i<=m;i++)
72     {
73         int x,y;
74         read(x);read(y);
75         add_edge(x,y);
76         add_edge(y,x);
77     }
78     for(int i=1;i<=n;i++)
79         if(low[i]==0)
80             tarjan(i,-1);    
81     printf("%d\n",ansnum);
82     for(int i=1;i<=n;i++)
83         if(ans[i]==1)
84             printf("%d ",i);
85     return 0;
86 }

update in 2017.11.7

补一份利用void类型实现的代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
	char c=getchar();int f=1,x=0;
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	x=x*10+c-48,c=getchar();return x*f;
}
struct node
{
	int u,v,nxt;
}edge[MAXN];
int head[MAXN];
int num=1;
inline void add_edge(int x,int y)
{
	edge[num].u=x;
	edge[num].v=y;
	edge[num].nxt=head[x];
	head[x]=num++;
}
int dfn[MAXN];//询问的时间 
int low[MAXN];//最早能追溯到的祖先 
int n,m,tot;//当前已经枚举了多少节点 
int ans[MAXN];//是否是割点 
int ansnum=0; 
void tarjan(int now,int fa)
{
	dfn[now]=low[now]=++tot;
	int ch=0;
	for(int i=head[now];i!=-1;i=edge[i].nxt)
	{
		if(low[edge[i].v]!=0)	
			low[now]=min(low[now],dfn[edge[i].v]);
		else if(low[edge[i].v]==0)
		{
			ch++;
			tarjan(edge[i].v,now);
			low[now]=min(low[now],low[edge[i].v]);
			if((fa==-1&&ch>1)||(fa!=-1&&(dfn[now]==low[edge[i].v]) ) )
			//一个点是根节点&&孩子的数量>1
			//或是这个点不是根节点且访问的点的祖先是它 
				if(ans[edge[i].u]==0)
					ans[edge[i].u]=1,ansnum++;
		}
	}
}
int main()
{
	memset(head,-1,sizeof(head));
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		add_edge(x,y);
		add_edge(y,x);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i,-1);
	printf("%d\n",ansnum);
	for(int i=1;i<=n;i++)
		if(ans[i])
			printf("%d ",i);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于深度学习的目标检测算法综述

    摘要: 从2014年开始,目标检测取得了巨大的突破。本文针对目前主流的目标检测方法进行简单的介绍,文章分为两个部分:第一部分介绍R Girshick提出的以R-...

    智能算法
  • 机器学习三人行(系列一)----机器学习花样入门

    写在前面 深度学习如火如荼,作为一个IT技术人员,不搞一下深度学习,总有一种活在上个世纪的感觉,因此笔者准备认认真真的搞一下深度学习,努力跟上时代的步伐。话说基...

    智能算法
  • 深度学习的主要应用举例

    参考资料 ? 最喜欢圆,尤其如此灵动 今天简单说一下 Deep Leaning 在各领域应用的几个例子,可以轻松地看一下它是怎么用在 Computer Visi...

    杨熹
  • 麻省理工学院用深度学习教会计算机预测未来

    【AI世代编者按】据外媒报道,通过部分基于人脑模型的算法,麻省理工学院的研究员让计算机可以通过分析照片去预测下一时刻的未来。 麻省理工学院计算机科学和人工智能实...

    智能算法
  • 理解这25个概念,你的人工智能,深度学习,机器学习才算入门!

    人工智能,深度学习,机器学习—无论你在做什么,如果你对它不是很了解的话—去学习它。否则的话不用三年你就跟不上时代的潮流了。 ——马克.库班 马克.库班的这个观点...

    智能算法
  • 机器视觉与计算机视觉的区别?

    计算机视觉与机器视觉,首先是应用场景不一样,就像@Vinjn张静 回答的那样:你把摄像头对着人就是CV,对着车间就是MV。 计算机视觉和机器视觉应用场景不同,就...

    智能算法
  • 2016年不可错过的21个深度学习视频、教程和课程

    几年之前,深度学习还是机器学习中一个不太受人关注的领域。随着最近神经网络和大数据概念的出现,很多复杂任务的实现已经成为可能。 目前,深度学习已经被应...

    智能算法
  • 深度学习|大师之作,必是精品

    1neural networks and deep learning 这是一个非常经典的神经网络和深度学习的教程,有完整的免费的电子书,网址如下: http:/...

    double
  • 深度学习入门之工具综述

    原文:Getting Started with Deep Learning: A REVIEW OF AVAILABLE TOOLS 作者: MATTHEW R...

    智能算法
  • 2017年关于深度学习的十大预测

    Carlos E. Perez对深度学习的2017年十大预测,让我们不妨看一看。有兴趣的话,可以在一年之后回顾这篇文章,看看这十大预测有多少准确命中:) ? 1...

    智能算法

扫码关注云+社区

领取腾讯云代金券