Hihocoder#1183 : 连通性一·割边与割点(连通图求割点和割边)

描述

还记得上次小Hi和小Ho学校被黑客攻击的事情么，那一次攻击最后造成了学校网络数据的丢失。为了避免再次出现这样的情况，学校决定对校园网络进行重新设计。

学校现在一共拥有N台服务器(编号1..N)以及M条连接，保证了任意两台服务器之间都能够通过连接直接或者间接的数据通讯。

当发生黑客攻击时，学校会立刻切断网络中的一条连接或是立刻关闭一台服务器，使得整个网络被隔离成两个独立的部分。

举个例子，对于以下的网络：

每两个点之间至少有一条路径连通，当切断边(3,4)的时候，可以发现，整个网络被隔离为{1，2，3}，{4，5，6}两个部分：

若关闭服务器3，则整个网络被隔离为{1，2}，{4，5，6}两个部分：

小Hi和小Ho想要知道，在学校的网络中有哪些连接和哪些点被关闭后，能够使得整个网络被隔离为两个部分。

在上面的例子中，满足条件的有边(3,4)，点3和点4。

 

提示：割边&割点

 

输入

第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000

第2..M+1行：2个正整数，u,v。表示存在一条边(u,v)，连接了u,v两台服务器。1≤u<v≤N

保证输入所有点之间至少有一条连通路径。

输出

第1行：若干整数，用空格隔开，表示满足要求的服务器编号。从小到大排列。若没有满足要求的点，该行输出Null

第2..k行：每行2个整数，(u,v)表示满足要求的边，u<v。所有边根据u的大小排序，u小的排在前，当u相同时，v小的排在前面。若没有满足要求的边，则不输出

样例输入

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

样例输出

3 4
3 4

       模板题，连通图求割点和割边。原理截取Hiho的解释。存个模板

割边：在连通图中，删除了连通图的某条边后，图不再连通。这样的边被称为割边，也叫做桥。

割点：在连通图中，删除了连通图的某个点以及与这个点相连的边后，图不再连通。这样的点被称为割点。

DFS搜索树：用DFS对图进行遍历时，按照遍历次序的不同，我们可以得到一棵DFS搜索树。在上面例子中，得到的搜索树为：

树边：在搜索树中的蓝色线所示，可理解为在DFS过程中访问未访问节点时所经过的边，也称为父子边

回边：在搜索树中的橙色线所示，可理解为在DFS过程中遇到已访问节点时所经过的边，也称为返祖边、后向边

观察DFS搜索树，我们可以发现有两类节点可以成为割点：

• 对根节点u，若其有两棵或两棵以上的子树，则该根结点u为割点；

• 对非叶子节点u（非根节点），若其中的某棵子树的节点均没有指向u的祖先节点的回边，说明删除u之后，根结点与该棵子树的节点不再连通；则节点u为割点。

对于根结点，显然很好处理；但是对于非叶子节点，怎么去判断有没有回边是一个值得深思的问题。

我们用dfn[u]记录节点u在DFS过程中被遍历到的次序号，low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点（即DFS次序号最小），那么low[u]的计算过程如下：

对于给的例子，其求出的dfn和low数组为：

id  1 2 3 4 5 6
dfn 1 2 3 4 5 6
low 1 1 1 4 4 4
		

可以发现，对于情况2，当(u,v)为树边且low[v]≥dfn[u]时，节点u才为割点。

而当(u,v)为树边且low[v]>dfn[u]时，表示v节点只能通过该边(u,v)与u连通，那么(u,v)即为割边。

void dfs(int u) {
	//记录dfs遍历次序
	static int counter = 0;	
	
	//记录节点u的子树数
	int children = 0;
	
	ArcNode *p = graph[u].firstArc;
	visit[u] = 1;

	//初始化dfn与low
	dfn[u] = low[u] = ++counter;

	for(; p != NULL; p = p->next) {
		int v = p->adjvex;
		
		//节点v未被访问，则(u,v)为树边
		if(!visit[v]) {
			children++;
			parent[v] = u;
			dfs(v);

			low[u] = min(low[u], low[v]);

			//case (1)
			if(parent[u] == NIL && children > 1) {
				printf("articulation point: %d\n", u);
			}

			//case (2)
			if(parent[u] != NIL && low[v] >= dfn[u]) {
				printf("articulation point: %d\n", u);
			}
			
			//bridge
			if(low[v] > dfn[u]) {
				printf("bridge: %d %d\n", u, v);
			}
		}

		//节点v已访问，则(u,v)为回边
		else if(v != parent[u]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
}

原题代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
vector<int>V[20005];
int ansNode[20005];
int dfn[20005];
int low[20005];
int visit[20005];
int parent[20005];
int have[20005];
int nn;
int nPoint;
int counter;	//记录dfs遍历次序
struct Bi
{
	int u,v;
}B[100005];
bool  cmp(Bi a,Bi b)
{
	if(a.u!=b.u)
		return a.u<b.u;
	else
		return a.v<b.v;
}
void dfs(int u) {
	//记录节点u的子树数
	int children = 0;

	visit[u] = 1;

	//初始化dfn与low
	dfn[u] = low[u] = ++counter;

	for(int i=0;i<V[u].size();i++) {
		int v = V[u][i];

		//节点v未被访问，则(u,v)为树边
		if(!visit[v]) {
			children++;
			parent[v] = u;
			dfs(v);

			low[u] = min(low[u], low[v]);

			//case (1)
			if(parent[u] == 0 && children > 1) {
				//printf("articulation point: %d\n", u);
				if(have[u]==0)
				{
					ansNode[nPoint++]=u;
					have[u]=1;
				}
			}

			//case (2)
			if(parent[u] != 0L && low[v] >= dfn[u]) {
				//printf("articulation point: %d\n", u);
				if(have[u]==0)
				{
					ansNode[nPoint++]=u;
					have[u]=1;
				}
			}

			//bridge
			if(low[v] > dfn[u]) {
				//printf("bridge: %d %d\n", u, v);
				if(u<v)
				{
					B[nn++].u=u;
					B[nn-1].v=v;
				}
				else
				{
					B[nn++].u=v;
					B[nn-1].v=u;
				}
			}
		}

		//节点v已访问，则(u,v)为回边
		else if(v != parent[u]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
}
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		memset(parent,0,sizeof(parent));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(visit,0,sizeof(visit));
		memset(have,0,sizeof(have));
		nn=0;
		nPoint=0;
        counter=0;
		for(int i=0;i<=n;i++)
		{
			V[i].clear();
		}
		int u,v;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d",&u,&v);
			V[u].push_back(v);
			V[v].push_back(u);
		}
		dfs(1);
		sort(ansNode,ansNode+nPoint);
		if(nPoint==0)
			cout<<"Null"<<endl;
		else
		{
			cout<<ansNode[0];
			for(int i=1;i<nPoint;i++)
			{
				cout<<" "<<ansNode[i];
			}
			cout<<endl;
		}
		sort(B,B+nn,cmp);
		for(int i=0;i<nn;i++)
		{
			cout<<B[i].u<<" "<<B[i].v<<endl;
		}
	}
}

今天的文章Hihocoder#1183 : 连通性一·割边与割点(连通图求割点和割边)分享到此就结束了，感谢您的阅读。