hihoCoder 1184-连通性二·边的双连通分量

hihoCoder 1184-连通性二·边的双连通分量
#1184 : 连通性二·边的双连通分量
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在基本的网络搭建完成后,学校为了方便管理还需要对所有的服务器进行编组,网络所的老师找到了小Hi和小Ho,希望他俩帮忙。
老师告诉小Hi和小Ho:根据现在网络的情况,我们要将服务器进行分组,对于同一个组的服务器,应当满足:当组内任意一个连接断开之后,不会影响组内服务器的连通性。在满足以上条件下,每个组内的服务器数量越多越好。
比如下面这个例子,一共有6个服务器和7条连接:

其中包含2个组,分别为{1,2,3},{4,5,6}。对{1,2,3}而言,当1-2断开后,仍然有1-3-2可以连接1和2;当2-3断开后,仍然有2-1-3可以连接2和3;当1-3断开后,仍然有1-2-3可以连接1和3。{4,5,6}这组也是一样。

老师把整个网络的情况告诉了小Hi和小Ho,小Hi和小Ho要计算出每一台服务器的分组信息。
提示:边的双连通分量
输入
第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行:1个整数,表示该网络的服务器组数。
第2行:N个整数,第i个数表示第i个服务器所属组内,编号最小的服务器的编号。比如分为{1,2,3},{4,5,6},则输出{1,1,1,4,4,4};若分为{1,4,5},{2,3,6}则输出{1,2,2,1,1,2}
样例输入
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
样例输出
2
1 1 1 4 4 4


边的双连通分量是指无向图的一个子图,当删除其中任意一条边后,不改变图内点的连通性。在hihoCoder week 52-1-连通性·一中,我们求过一个图的桥,当删除所有桥之后,图肯定不连通了,此时剩下的每一个区域就是我们要求的边的双连通分量。
所以简单的方法就是先用上一题的方法求出桥,然后删除所有桥,进行DFS遍历求出边的双连通分量。但是提示给出了一个更巧妙的方法,在求桥的过程中,使用一个堆栈保存遍历过的点,当low[u]==dfn[u]时,u点通过回边追溯到的最早节点是其本身,说明u和parent[u]的同伙只有唯一的一条边(parent[u],u)相连,且这条边是桥,那么此时栈内在u之前入栈的点和u被该桥分割开,也就是说从u到栈顶的所有元素是一组。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
const int kMaxN = 20005;
int n, m;
vector<vector<int>> graph;
stack<int> stk;
int visit[kMaxN];
int dfn[kMaxN];
int low[kMaxN];
int parent[kMaxN];
int belong[kMaxN];
int bridge_num=0;
void dfs(int u) {
	//记录dfs遍历次序
	static int counter = 0;
	//记录节点u的子树数
	int children = 0;
	visit[u] = 1;
	//初始化dfn与low
	dfn[u] = low[u] = ++counter;
	//将u加入栈
	stk.push(u);
	for (int i = 0; i < graph[u].size(); i++) {
		int v = graph[u][i];
		//节点v未被访问,则(u,v)为树边
		if (visit[v] == 0) {
			children++;
			parent[v] = u;
			dfs(v);
			low[u] = min(low[u], low[v]);
			//bridge
			if (low[v] > dfn[u]) {
				bridge_num++;
			}
		}
		//节点v已访问,则(u,v)为回边
		else if (v != parent[u]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (low[u] == dfn[u])
	{
		int min_id = u;
		vector<int> member;
		while (stk.top() != u)
		{
			min_id = min(min_id, stk.top());
			member.push_back(stk.top());
			stk.pop();
		}
		member.push_back(u);
		stk.pop();
		for (int i = 0; i < member.size(); i++)
			belong[member[i]] = min_id;
	}
}
int main()
{
	//freopen("input.txt", "r",stdin);
	scanf("%d %d", &n, &m);
	graph.resize(n + 1);
	int u, v;
	while (m--)
	{
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	dfs(1);
	printf("%dn", bridge_num+1);
	for (int i = 1; i <= n; i++)
		printf("%d ", belong[i]);
	return 0;
}

本代码提交AC,用时69MS,内存5MB。
有一点需要提醒,题目要求同一个联通分量用内部最小结点来表示,这里不能想当然的认为当low[u]=dfn[u]时,最小节点是u,万一是下图,2和3比6后进入堆栈,也就是2和3在堆栈中的位置在6的上面,当回溯到6号节点时,有low[6]==dfn[6],但是右边的联通分量中最小节点显然是2,所以还是老老实实遍历求最小值。

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.