Tag Archives: 点的双连通分量

hihoCoder week 55-1-连通性·四

hihoCoder week 55-1-连通性·四
题目1 : 连通性·四
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho从约翰家回到学校时,网络所的老师又找到了小Hi和小Ho。
老师告诉小Hi和小Ho:之前的分组出了点问题,当服务器(上次是连接)发生宕机的时候,在同一组的服务器有可能连接不上,所以他们希望重新进行一次分组。这一次老师希望对连接进行分组,并把一个组内的所有连接关联的服务器也视为这个组内的服务器(注意一个服务器可能属于多个组)。
这一次的条件是对于同一个组满足:当组内任意一个服务器宕机之后,不会影响组内其他服务器的连通性。在满足以上条件下,每个组内的边数量越多越好。
比如下面这个例子,一共有6个服务器和7条连接:

其中包含3个组,分别为{(1,2),(2,3),(3,1)},{(4,5),(5,6),(4,6)},{(3,4)}。对{(1,2),(2,3),(3,1)}而言,和该组边相关联的有{1,2,3}三个服务器:当1宕机后,仍然有2-3可以连接2和3;当2宕机后,仍然有1-3可以连接1和3;当3宕机后,仍然有1-2可以连接1和2。

老师把整个网络的情况告诉了小Hi和小Ho,希望小Hi和小Ho统计一下一共有多少个分组。
提示:点的双连通分量
输入
第1行:2个正整数,N,M。表示点的数量N,边的数量M。1≤N≤20,000, 1≤M≤100,000
第2..M+1行:2个正整数,u,v。第i+1行表示存在一条边(u,v),编号为i,连接了u,v两台服务器。1≤u<v≤N
保证输入所有点之间至少有一条连通路径。
输出
第1行:1个整数,表示该网络的连接组数。
第2行:M个整数,第i个数表示第i条连接所属组内,编号最小的连接的编号。比如分为{(1,2)[1],(2,3)[3],(3,1)[2]},{(4,5)[5],(5,6)[7],(4,6)[6]},{(3,4)[4]},方括号内表示编号,则输出{1,1,1,4,5,5,5}。
样例输入
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
样例输出
3
1 1 1 4 5 5 5


这一题求点的双连通分量,结果是边集;上一题求了边的双连通分量,结果是点集。
点的双连通分量是指子图中去掉一个点之后还连通,求解方法还是Tarjan,和之前的题目类似。需要注意的是,提示中的伪代码有错误,有好几个地方没有将边添加到堆栈中,正确的伪代码在这里
本题要求输出连通分量中边的最小编号,所以输入的时候要记录边的编号,并且保证当弹出堆栈时,能快速知道这是哪一条边,简单的方法是将边(u,v)映射成一个整数x,因为u,v≤20,000,所以可以令hash=max(u,v)*100000+min(u,v)。
因为点的双连通分量数等于割点数量加1,如果DFS求到有2个割点,实际有3个连通分量,所以当DFS结束时,所有没有标记的边就是最后一个连通分量。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
const int kMaxN = 20005;
const int kMaxM = 100005;
map<int, int> edge_code;
map<int, int> ans;
vector<vector<int> > graph;
vector<int> edges;
stack<int> stk;
bool visit[kMaxN];
int low[kMaxN];
int dfn[kMaxN];
int parent[kMaxN];
int n, m;
int points=0;
int HashEdge(int x, int y)
{
	if (x > y)
		return x * 100000 + y;
	else
		return y * 100000 + x;
}
void dfs(int u) {
	//记录dfs遍历次序
	static int counter = 0;
	//记录节点u的子树数
	int children = 0;
	visit[u] = true;
	//初始化dfn与low
	dfn[u] = low[u] = ++counter;
	for (int i = 0; i < graph[u].size(); i++) {
		int v = graph[u][i];
		int e = HashEdge(u, v);
		if (ans.find(e)!=ans.end())
			continue;
		//节点v未被访问,则(u,v)为树边
		if (!visit[v]) {
			children++;
			parent[v] = u;
			stk.push(e);
			dfs(v);
			low[u] = min(low[u], low[v]);
			//case (1)
			if (parent[u] == 0 && children > 1) {
				points++;
				int tmp = -1, id = kMaxM;
				vector<int> tmp_edges;
				do{
					tmp = stk.top();
					stk.pop();
					tmp_edges.push_back(tmp);
					if (edge_code[tmp] < id)
						id = edge_code[tmp];
				} while (tmp != e);
				for (int i = 0; i < tmp_edges.size(); i++)
					ans.insert(make_pair(tmp_edges[i], id));
			}
			//case (2)
			if (parent[u] != 0 && low[v] >= dfn[u]) {
				points++;
				int tmp = -1, id = kMaxM;
				vector<int> tmp_edges;
				do{
					tmp = stk.top();
					stk.pop();
					tmp_edges.push_back(tmp);
					if (edge_code[tmp] < id)
						id = edge_code[tmp];
				} while (tmp != e);
				for (int i = 0; i < tmp_edges.size(); i++)
					ans.insert(make_pair(tmp_edges[i], id));
			}
		}
		//节点v已访问,则(u,v)为回边
		else if (v != parent[u]) {
			stk.push(e);
			low[u] = min(low[u], dfn[v]);
		}
	}
}
int main()
{
	scanf("%d %d", &n, &m);
	graph.resize(n + 1);
	int u, v,tmp;
	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
		tmp = HashEdge(u, v);
		edges.push_back(tmp);
		edge_code.insert(make_pair(tmp, i));
	}
	dfs(1);
	//求解最后一个连通分量
	int max_tmp = kMaxM;
	for (int i = 1; i <= m; i++)
	{
		if (ans.find(edges[i - 1]) == ans.end())
			if (edge_code[edges[i - 1]] < max_tmp)
				max_tmp = edge_code[edges[i - 1]];
	}
	printf("%dn", points + 1);
	for (int i = 1; i <= m; i++)
		printf("%d ", ans[edges[i - 1]] == 0 ? max_tmp : ans[edges[i - 1]]);
	return 0;
}

本代码提交AC,用时240MS,内存10MB。