Monthly Archives: June 2015

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。

hihoCoder week 51-1-欧拉路·三

hihoCoder week 51-1-欧拉路·三
题目1 : 欧拉路·三
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho破解了一道又一道难题,终于来到了最后一关。只要打开眼前的宝箱就可以通关这个游戏了。
宝箱被一种奇怪的机关锁住:

这个机关是一个圆环,一共有2^N个区域,每个区域都可以改变颜色,在黑白两种颜色之间切换。
小Ho控制主角在周围探索了一下,果然又发现了一个纸片:
机关黑色的部分表示为1,白色的部分表示为0,逆时针连续N个区域表示一个二进制数。打开机关的条件是合理调整圆环黑白两种颜色的分布,使得机关能够表示0~2^N-1所有的数字。
我尝试了很多次,终究没有办法打开,只得在此写下机关破解之法。
——By 无名的冒险者
小Ho:这什么意思啊?
小Hi:我给你举个例子,假如N=3,我们通过顺时针转动,可以使得正下方的3个区域表示为:

因为黑色表示为1,白色表示为0。则上面三个状态分别对应了二进制(001),(010),(101)
每转动一个区域,可以得到一个新的数字。一共可以转动2^N次,也就是2^N个数字。我们要调整黑白区域的位置,使得这2^N个数字恰好是0~2^N-1
小Ho:我懂了。若N=2,则将环上的黑白色块调整为"黑黑白白",对应了"1100"。依次是"11","10","00","01"四个数字,正好是0~3。那么这个"黑黑白白"就可以打开机关了咯?
小Hi:我想应该是的。
小Ho:好像不是很难的样子,我来试试!
提示:有向图欧拉回路
输入
第1行:1个正整数,N。1≤N≤15
输出
第1行:1个长度为2^N的01串,表示一种符合要求的分布方案
样例输入
3
样例输出
00010111


本题是欧拉路的判定、无向图欧拉路的求解的更进一步,有向图欧拉路的求解。
在有向图中找欧拉路的算法和无向图中相同,还是Fleury算法,只不过这一题需要自己构造有向图。构造的方法详见题目提示,我一开始根据

对于任意两个点,如果点i,点j满足点i的后n-2个数字和点j的前n-2个数字相同,则我们连接有向边(i,j)。

这句话来构造的,略显麻烦。因为

而我们构造的图,由构造方法可以知道对于任意一个点,其入度一定为2,出度一定为2。所以它必定存在欧拉回路。

所以对于每一个点,它有且只有两个出度,我们只需要求出这两个出度即可,不需要0~n-1一个一个点判断。用二进制表示,对于一个特定的点x=a_1a_2...a_n,假设x出边指向的点为y和z,则y,z的前n-1位和x的后n-1位是相同的,也即y=a_2a_3...a_{n-1}0, z=a_2a_3...a_{n-1}1。用公式表示就是y=(x<<1)&(111...1),x左移一位,与上n个1,z=y+1。
把有向图构造好之后,按部就班用Fleury算法求解,再把结果倒序输出,输出的时候只要输出每个点的最后一位就行了。
完整代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxN = 16;
int edge[1 << kMaxN][2];
int path[1 << kMaxN];
int path_size = 0;
int n;
void MakeGraph()
{
	memset(edge, -1, sizeof(edge));
	int nn = 1 << (n - 1);
	for (int i = 0; i < nn; i++)
	{
		edge[i][0] = (i << 1)&(nn - 1);
		edge[i][1] = edge[i][0] + 1;
	}
}
void DFS(int p)
{
	for (int i = 0; i < 2; i++)
	{
		int q = edge[p][i];
		if (q != -1)
		{
			edge[p][i] = -1;
			DFS(q);
		}
	}
	path[path_size++] = p;
}
int main()
{
	scanf("%d", &n);
	if (n == 1)
	{
		printf("01");
		return 0;
	}
	else if (n == 2)
	{
		printf("1100");
		return 0;
	}
	MakeGraph();
	DFS(0);
	while (--path_size)
		printf("%d", path[path_size] & 1);
	return 0;
}

本代码提交AC,用时8MS,内存1MB。

hihoCoder 1121-二分图一•二分图判定

hihoCoder 1121-二分图一•二分图判定
#1121 : 二分图一•二分图判定
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
大家好,我是小Hi和小Ho的小伙伴Nettle,从这个星期开始由我来完成我们的Weekly。新年回家,又到了一年一度大龄剩男剩女的相亲时间。Nettle去姑姑家玩的时候看到了一张姑姑写的相亲情况表,上面都是姑姑介绍相亲的剩男剩女们。每行有2个名字,表示这两个人有一场相亲。由于姑姑年龄比较大了记性不是太好,加上相亲的人很多,所以姑姑一时也想不起来其中有些人的性别。因此她拜托我检查一下相亲表里面有没有错误的记录,即是否把两个同性安排了相亲。OK,让我们愉快的暴力搜索吧!才怪咧。对于拿到的相亲情况表,我们不妨将其转化成一个图。将每一个人作为一个点(编号1..N),若两个人之间有一场相亲,则在对应的点之间连接一条无向边。(如下图)
因为相亲总是在男女之间进行的,所以每一条边的两边对应的人总是不同性别。假设表示男性的节点染成白色,女性的节点染色黑色。对于得到的无向图来说,即每一条边的两端一定是一白一黑。如果存在一条边两端同为白色或者黑色,则表示这一条边所表示的记录有误。由于我们并不知道每个人的性别,我们的问题就转化为判定是否存在一个合理的染色方案,使得我们所建立的无向图满足每一条边两端的顶点颜色都不相同。那么,我们不妨将所有的点初始为未染色的状态。随机选择一个点,将其染成白色。再以它为起点,将所有相邻的点染成黑色。再以这些黑色的点为起点,将所有与其相邻未染色的点染成白色。不断重复直到整个图都染色完成。(如下图)
在染色的过程中,我们应该怎样发现错误的记录呢?相信你一定发现了吧。对于一个已经染色的点,如果存在一个与它相邻的已染色点和它的颜色相同,那么就一定存在一条错误的记录。(如上图的4,5节点)到此我们就得到了整个图的算法:选取一个未染色的点u进行染色
遍历u的相邻节点v:若v未染色,则染色成与u不同的颜色,并对v重复第2步;若v已经染色,如果 u和v颜色相同,判定不可行退出遍历。
若所有节点均已染色,则判定可行。
接下来就动手写写吧!
输入
第1行:1个正整数T(1≤T≤10)
接下来T组数据,每组数据按照以下格式给出:
第1行:2个正整数N,M(1≤N≤10,000,1≤M≤40,000)
第2..M+1行:每行两个整数u,v表示u和v之间有一条边
输出
第1..T行:第i行表示第i组数据是否有误。如果是正确的数据输出”Correct”,否则输出”Wrong”
样例输入
2
5 5
1 2
1 3
3 4
5 2
1 5
5 5
1 2
1 3
3 4
5 2
3 5
样例输出
Wrong
Correct


本题考察二分图的判定,最简单的染色问题。
提示使用暴力搜索,其实就是BFS广度优先搜索。有一点需要注意的是,无向图可能有多个连通分量,比如下图。

此图有两个连通分量,且两个分量都可以相亲成功,但如果只从第1点开始BFS,则不能遍历到第二个分量,导致失败。所以需要对每一个还未染色的点都开始BFS,如果都尝试过了还有点未染色,二分图判定失败;否则成功。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n, m;
vector<int> colored;
vector<vector<int>> path;
bool BFS(int start)
{
	colored[start] = 0;
	int num_colored = 1;
	queue<int> point;
	point.push(start);
	while (!point.empty())
	{
		int current = point.front();
		point.pop();
		for (int i = 0; i < path[current].size(); i++)
		{
			if (colored[path[current][i]] == -1)
			{
				if (colored[current] == 0)
					colored[path[current][i]] = 1;
				else if (colored[current] == 1)
					colored[path[current][i]] = 0;
				num_colored++;
				point.push(path[current][i]);
			}
			else if (colored[current] == colored[path[current][i]])
				return false;
		}
	}
	return true;
}
bool Check()
{
	for (int i = 1; i <= n; i++)
		if (colored[i] == -1)
			if (!BFS(i))
				return false;
	return true;
}
int main()
{
	int t,u,v;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d %d", &n, &m);
		colored.clear();
		colored.resize(n + 1, -1);
		path.clear();
		path.resize(n + 1);
		for (int i = 0; i < m; i++)
		{
			scanf("%d %d", &u, &v);
			path[u].push_back(v);
			path[v].push_back(u);
		}
		if (Check())
			printf("Correctn");
		else
			printf("Wrongn");
	}
	return 0;
}

本代码提交AC,用时134MS,内存6MB。

hihoCoder week 50-1-欧拉路·二

hihoCoder week 50-1-欧拉路·二
题目1 : 欧拉路·二
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在上一回中小Hi和小Ho控制着主角收集了分散在各个木桥上的道具,这些道具其实是一块一块骨牌。

主角继续往前走,面前出现了一座石桥,石桥的尽头有一道火焰墙,似乎无法通过。
小Hi注意到在桥头有一张小纸片,于是控制主角捡起了这张纸片,只见上面写着:
将M块骨牌首尾相连放置于石桥的凹糟中,即可关闭火焰墙。切记骨牌需要数字相同才能连接。
——By 无名的冒险者
小Hi和小Ho打开了主角的道具栏,发现主角恰好拥有M快骨牌。
小Ho:也就是说要把所有骨牌都放在凹槽中才能关闭火焰墙,数字相同是什么意思?
小Hi:你看,每一块骨牌两端各有一个数字,大概是只有当数字相同时才可以相连放置,比如:

小Ho:原来如此,那么我们先看看能不能把所有的骨牌连接起来吧。
提示:Fleury算法求欧拉路径
输入
第1行:2个正整数,N,M。分别表示骨牌上出现的最大数字和骨牌数量。1≤N≤1,000,1≤M≤5,000
第2..M+1行:每行2个整数,u,v。第i+1行表示第i块骨牌两端的数字(u,v),1≤u,v≤N
输出
第1行:m+1个数字,表示骨牌首尾相连后的数字
比如骨牌连接的状态为(1,5)(5,3)(3,2)(2,4)(4,3),则输出"1 5 3 2 4 3"
你可以输出任意一组合法的解。
样例输入
5 5
3 5
3 2
4 2
3 4
5 1
样例输出
1 5 3 4 2 3


上一周学习了怎样判断欧拉通路,这周要给出一条具体的欧拉通路。
欧拉通路的求解使用Fleury算法,其伪代码如下:

DFS(u):
	While (u存在未被删除的边e(u,v))
		删除边e(u,v)
		DFS(v)
	End
	PathSize ← PathSize + 1
	Path[ PathSize ] ← u

非常简洁漂亮,本题完整代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxN = 1005,kMaxM=5005;
int n, m,path_size=0;
int path[kMaxM];//是kMaxM而非kMaxN
int edge[kMaxN][kMaxN];
void dfs(int p)
{
	for (int i = 1; i <= n; i++)
	{
		if (edge[p][i]>0)
		{
			edge[p][i]--;
			edge[i][p]--;
			dfs(i);
		}
	}
	path[path_size++] = p;
}
int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	int u, v;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &u, &v);
		edge[u][v]++;//防止有重边
		edge[v][u]++;
	}
	dfs(1);
	for (int i = 0; i < path_size; i++)
		printf("%d ", path[i]);
	return 0;
}

本代码提交AC,用时15MS,内存3MB。需要提醒的是,path的实际大小是m+1,而非n;另外为了防止有重边出现,edge用于记录边的数量,而非是否有边存在。
AC之后我还尝试了先找出欧拉通路的起点,再从起点开始dfs的方法,这种方法并没有更快,因为不论是从哪个点开始dfs,每个点的for循环都要完整执行,所以时间并不会减少,反而会由于寻找起点而增加时间。

hihoCoder week 49-1-欧拉路·一

hihoCoder week 49-1-欧拉路·一
题目1 : 欧拉路·一
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho最近在玩一个解密类的游戏,他们需要控制角色在一片原始丛林里面探险,收集道具,并找到最后的宝藏。现在他们控制的角色来到了一个很大的湖边。湖上有N个小岛(编号1..N),以及连接小岛的M座木桥。每座木桥上各有一个宝箱,里面似乎装着什么道具。
湖边还有一个船夫,船夫告诉主角。他可以载着主角到任意一个岛上,并且可以从任意一个岛上再载着主角回到湖边,但是主角只有一次来回的机会。同时船夫告诉主角,连接岛屿之间的木桥很脆弱,走过一次之后就会断掉。
因为不知道宝箱内有什么道具,小Hi和小Ho觉得如果能把所有的道具收集齐肯定是最好的,那么对于当前岛屿和木桥的情况,能否将所有道具收集齐呢?
举个例子,比如一个由6个小岛和8座桥组成的地图:

主角可以先到达4号小岛,然后按照4->1->2->4->5->6->3->2->5的顺序到达5号小岛,然后船夫到5号小岛将主角接回湖边。这样主角就将所有桥上的道具都收集齐了。
提示:欧拉路的判定
输入
第1行:2个正整数,N,M。分别表示岛屿数量和木桥数量。1≤N≤10,000,1≤M≤50,000
第2..M+1行:每行2个整数,u,v。表示有一座木桥连接着编号为u和编号为v的岛屿,两个岛之间可能有多座桥。1≤u,v≤N
输出
第1行:1个字符串,如果能收集齐所有的道具输出“Full”,否则输出”Part”。
样例输入
6 8
1 2
1 4
2 4
2 5
2 3
3 6
4 5
5 6
样例输出
Full


本题考察无向图欧拉路的判断。
关于有向图和无向图欧拉(回)路的介绍,请看POJ Problem 1386: Play on Words。总结一下就是先用并查集判断无向图是否连通,然后判断奇数度的节点个数是否为0或2。完整代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
const int kMax = 10005;
int n, m;
int degree[kMax];
int father[kMax];
int Find(int x)
{
	return x == father[x] ? x : (father[x] = Find(father[x]));
}
void Union(int x, int y)
{
	father[Find(x)] = Find(y);
}
void Init()
{
	for (int i = 1; i <= n; i++)
		father[i] = i;
}
bool IsConnected()
{
	for (int i = 1; i <= n; i++)
		if (father[i] != father[1])
			return false;
	return true;
}
bool IsEuler()
{
	int odd = 0;
	for (int i = 1; i <= n; i++)
		if (degree[i] & 1)
			odd++;
	if (odd == 0 || odd == 2)
		return true;
	return false;
}
int main()
{
	scanf("%d %d", &n, &m);
	int u, v;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &u, &v);
		degree[u]++;
		degree[v]++;
		Union(u, v);
	}
	if (IsConnected())
	{
		if (IsEuler())
			printf("Full\n");
		else
			printf("Part\n");
	}
	else
		printf("Part\n");
	return 0;
}

本代码提交AC,用时13MS,内存1MB。
总结:
判断图中是否存在环路详细介绍可看这里
1. 无向图:依次删除图中度数为0或1的点及其关联的边,循环结束,如果还有未删除的点,则存在回路。
2. 有向图:拓扑排序,依次删除图中入度为0的点及其关联的出边,循环结束,如果还有未删除的点,则存在回路。
判断图是否连通
1. 无向图:使用并查集,最终如果所有节点的父亲都相同,则无向图是连通的。
2. 有向图:判断有向图是否强连通貌似很复杂,Kosaraju算法判断强连通图以及有向图强连通分量的Tarjan算法