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。

hihoCoder 1185-连通性·三

hihoCoder 1185-连通性·三
#1185 : 连通性·三
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
暑假到了!!小Hi和小Ho为了体验生活,来到了住在大草原的约翰家。今天一大早,约翰因为有事要出去,就拜托小Hi和小Ho忙帮放牧。
约翰家一共有N个草场,每个草场有容量为W[i]的牧草,N个草场之间有M条单向的路径。
小Hi和小Ho需要将牛羊群赶到草场上,当他们吃完一个草场牧草后,继续前往其他草场。当没有可以到达的草场或是能够到达的草场都已经被吃光了之后,小hi和小Ho就把牛羊群赶回家。
一开始小Hi和小Ho在1号草场,在回家之前,牛羊群最多能吃掉多少牧草?
举个例子:

图中每个点表示一个草场,上部分数字表示编号,下部分表示草场的牧草数量w。
在1吃完草之后,小Hi和小Ho可以选择把牛羊群赶到2或者3,假设小Hi和小Ho把牛羊群赶到2:
吃完草场2之后,只能到草场4,当4吃完后没有可以到达的草场,所以小Hi和小Ho就把牛羊群赶回家。
若选择从1到3,则可以到达5,6:
选择5的话,吃完之后只能直接回家。若选择6,还可以再通过6回到3,再到5。
所以该图可以选择的路线有3条:
1->2->4                      total: 11
1->3->5                      total: 9
1->3->6->3->5           total: 13
所以最多能够吃到的牧草数量为13。
本题改编自USACO月赛金组
提示:强连通分量
输入
第1行:2个正整数,N,M。表示点的数量N,边的数量M。1≤N≤20,000, 1≤M≤100,000
第2行:N个正整数,第i个整数表示第i个牧场的草量w[i]。1≤w[i]≤100,000
第3..M+2行:2个正整数,u,v。表示存在一条从u到v的单向路径。1≤u,v≤N
输出
第1行:1个整数,最多能够吃到的牧草数量。
样例输入
6 6
2 4 3 5 4 4
1 2
2 4
1 3
3 5
3 6
6 3
样例输出
13


本题将图换成了有向图。首先求解有向图中的强连通分量,强连通分量是指有向图的子图中,两两点之间互相可达,求解方法和之前两道题的方法类似,还是用Tarjan算法,可以参考BYVoid的博客
求解到所有强连通分量之后,将每个强连通分量缩成一个点,构成一个新的有向图,缩点的草量等于该强连通分量草量之和。
假设原图点1在新图中的缩点编号为u,则得到一个新的有向图之后,问题就转换为在新图中从点u开始遍历,求经过路径的草量之和最大是多少。这一步可以用常规DFS方法求解,也可以用提示中的拓扑排序求解,我觉得DFS更好理解一点。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int kMaxN = 20005;
int n, m,new_n=0;
stack<int> stk;
vector<vector<int>> graph;
vector<vector<int>> new_graph;
int w[kMaxN];
int new_w[kMaxN];
int dfn[kMaxN];//DFS时的序号,如果!=0说明已经被访问过了
int low[kMaxN];
bool in_stack[kMaxN];
int belong[kMaxN];
int grass[kMaxN];
int in_degree[kMaxN];
bool visit[kMaxN];
int rs = 0;
void Tarjan(int u) {
	//记录dfs遍历次序
	static int counter = 0;
	stk.push(u);
	in_stack[u] = true;
	//初始化dfn与low
	dfn[u] = low[u] = ++counter;
	for (int i = 0; i < graph[u].size(); i++) {
		int v = graph[u][i];
		//节点v未被访问
		if (dfn[v] == 0) {
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		//节点v已访问,则(u,v)为回边
		else if (in_stack[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u])
	{
		new_n++;
		int temp;
		do{
			temp = stk.top();
			stk.pop();
			new_w[new_n] += w[temp];
			in_stack[temp] = false;
			belong[temp] = new_n;
		} while (temp != u);
	}
}
void RebuildGraph()
{
	//重建邻接矩阵
	new_graph.resize(new_n + 1);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < graph[i].size(); j++)
		{
			if (belong[i] != belong[graph[i][j]])
			{
				new_graph[belong[i]].push_back(belong[graph[i][j]]);//有边
				in_degree[belong[graph[i][j]]]++;
			}
		}
	}
}
int TopSort()
{
	queue<int> zero_in_degree;
	for (int i = 1; i <= new_n; i++)
		if (in_degree[i] == 0)
			zero_in_degree.push(i);
	int ans = 0;
	while (!zero_in_degree.empty())
	{
		int node = zero_in_degree.front();
		zero_in_degree.pop();
		if (visit[node])//点belong[1]能访问到的点才计算,否则这步不执行,grass[node]为0
			grass[node] += new_w[node];
		if (grass[node] > ans)
			ans = grass[node];
		for (int i = 0; i < new_graph[node].size(); i++)
		{
			int node2 = new_graph[node][i];
			if (grass[node]>grass[node2])
				grass[node2] = grass[node];
			if (--in_degree[node2] == 0)
				zero_in_degree.push(node2);
		}
	}
	return ans;
}
//记录哪些点是belong[1]能访问到的
void Visit()
{
	queue<int> q;
	q.push(belong[1]);
	while (!q.empty())
	{
		int f = q.front();
		q.pop();
		visit[f] = true;
		for (int i = 0; i < new_graph[f].size(); i++)
			q.push(new_graph[f][i]);
	}
}
void DFS(int u,int g)
{
	if (rs < g)
		rs = g;
	for (int i = 0; i < new_graph[u].size(); i++)
		DFS(new_graph[u][i], g + new_w[new_graph[u][i]]);
}
int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	graph.resize(n + 1);
	for (int i = 1; i <= n; i++)
		scanf("%d", &w[i]);
	int u, v;
	while (m--)
	{
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
	}
	for (int i = 1; i <= n;i++)//每个点都要尝试一次
		if (dfn[i]==0)
			Tarjan(i);
	RebuildGraph();
	Visit();
	printf("%dn", TopSort());
	//深搜的方法也可以
	//DFS(belong[1], new_w[belong[1]]);
	//printf("%dn", rs);
	return 0;
}

本代码提交AC,用时57MS,内存3MB。
有两点需要注意:第一,因为有些点可能是1到达不了的,这样Tarjan(1)就不能得到所有的强连通分量,所以需要for循环尝试每一个点;第二,在拓扑排序的时候,如果某个缩点是belong[1]无法访问的,则其草量为0。

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,所以还是老老实实遍历求最小值。

hihoCoder week 52-1-连通性·一

hihoCoder week 52-1-连通性·一
题目1 : 连通性·一
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
还记得上次小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


本题要求一个连通图的割边和割点,使用Tarjan算法,提示已经把dfs主要代码写了,完善一下即可。

主要要理解上面的递推公式。首先理解dfn和low的含义,dfn[u]记录节点u在DFS过程中被遍历到的次序号,low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点(即DFS次序号最小)。
上图的第一个式子,当(u,v)为树边时,low[u]表明u能追溯到的最早节点,low[v]表明u的子树(v就是u的子树的根)能追溯到的最早节点,所以根据low[u]的定义有low[u]=min(low[u],low[v])。
上图的第二个式子,当(u,v)为回边时,因为low[u]的定义就是u通过非父子边(回边)追溯最早的节点,所以既然(u,v)为回边,自然的low[u]=min(low[u],dfn[v])。
另外注意输出格式,点要从小到大排列;边(u,v)保证u<v,以u从小到大排列,再以v从小到大排列。完整代码如下:

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
const int kMaxN = 20005;
int n, m;
typedef struct edge
{
	int x, y;
	bool operator<(const edge& p)const//如果要加入到set中,需要重载<
	{
		return (this->x<p.x) || ((this->x == p.x) && (this->y<p.y));
	}
};
set<int> points;
set<edge> edges;
vector<vector<int>> graph;
int visit[kMaxN];
int dfn[kMaxN];
int low[kMaxN];
int parent[kMaxN];
void dfs(int u) {
	//记录dfs遍历次序
	static int counter = 0;
	//记录节点u的子树数
	int children = 0;
	visit[u] = 1;
	//初始化dfn与low
	dfn[u] = low[u] = ++counter;
	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]);
			//case (1)
			if (parent[u] == 0 && children > 1) {
				points.insert(u);
			}
			//case (2)
			if (parent[u] != 0 && low[v] >= dfn[u]) {
				points.insert(u);
			}
			//bridge
			if (low[v] > dfn[u]) {
				edge e;
				e.x = u;
				e.y = v;
				if (u > v)
				{
					e.x = v;
					e.y = u;
				}
				edges.insert(e);
			}
		}
		//节点v已访问,则(u,v)为回边
		else if (v != parent[u]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
}
int main()
{
	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);
	if (points.size() == 0)
		printf("Null\n");
	else
	{
		set<int>::iterator it = points.begin();
		while (it != points.end())
		{
			printf("%d ", *it);
			it++;
		}
		printf("\n");
	}
	if (edges.size() > 0)
	{
		set<edge>::iterator it = edges.begin();
		while (it != edges.end())
		{
			printf("%d %d\n", (*it).x, (*it).y);
			it++;
		}
	}
	return 0;
}

本代码提交AC,用时76MS,内存7MB。