Tag Archives: 并查集

LeetCode Friend Circles

LeetCode Friend Circles
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are directfriends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Example 1:

Input:
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.

Example 2:

Input:
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

  1. N is in range [1,200].
  2. M[i][i] = 1 for all students.
  3. If M[i][j] = 1, then M[j][i] = 1.

给定一个矩阵,M[i][j]=1表示i和j有直接关系,如果i和j有直接关系,j和k有直接关系,则i和k有间接关系。问这个矩阵共有多少个关系网。
简单题,有两种解法。第一种解法是DFS或者BFS,每次把能搜索到的点标记为一个新的关系网,直到所有点都属于一个关系网。但是无论DFS还是BFS,复杂度都比较高。
这种题应该条件反射想到并查集,只要M[i][j]=1,则把i和j union起来,最后看一下有多少个代表就好了。这种解法非常简单,代码如下:

class Solution {
private:
	int n;
	vector<int> parent;
	void init() {
		parent.resize(n);
		for (int i = 0; i < n; ++i) {
			parent[i] = i;
		}
	}
	int find_set(int x) {
		if (parent[x] != x)
			parent[x] = find_set(parent[x]);
		return parent[x];
	}
	void union_set(int u, int v) {
		parent[find_set(u)] = find_set(v);
	}
public:
	int findCircleNum(vector<vector<int>>& M) {
		n = M.size();
		init();
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (M[i][j] == 1) {
					union_set(i, j);
				}
			}
		}
		set<int> circles;
		for (int i = 0; i < n; ++i)circles.insert(find_set(i)); // 注意最后还要find一下找到代表
		return circles.size();
	}
};

本代码提交AC,用时19MS。

hihoCoder 1495-矩形分割

hihoCoder 1495-矩形分割

#1495 : 矩形分割

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi有一块由NxM个单位正方形组成的矩形。现在小Ho在某些单位正方形上画了一道分割线,这条分割线或者是单位正方形的主对角线(用'\'表示),或者是副对角线(用'/'表示)。
现在小Hi想知道这些分割线把NxM的矩形分割成了多少块区域。
例如

/\
\/

就把2x2的矩形分成了5个区域。

/\/\
\  /
 \/\

把3x4的矩形分成了7个区域。

输入

第一包含两个整数N和M。(1 <= N, M <= 100)
以下N行每行包含M个字符。每个字符只可能是/\或者空格。

输出

分割成的区域数目。

样例输入
3 4
/\/\
\  /
 \/\
样例输出
7

本题又是一个考察并查集的题,再一次栽在了并查集!
给定一个由n*m个小正方形组成的大矩形,现在在某些小正方形上画一道分隔线,该分隔线可能是小正方形的主对角线\,也可能是副对角线/。问经过分隔之后,把大矩形分隔成了多少块区域。
判断平面区域个数问题,一般都可以转化为并查集的问题,但是这题相对上一次的并查集又进了一步,这题应该算是三维的并查集了。
对于小正方形的每个点,我们用三维信息来表示(x,y,z),其中x,y表示顶点所在小正方形的行号和列号,z表示该顶点在该小正方形中的位置,坐标从左上角开始顺时针递增,如下图。

0-----1
|     |
|     |
3-----2

初始时,每个顶点自成一体,所以par[i]=i。
但是因为画的分隔线只能是对角线,所以相邻两个正方形中的共享边肯定属于同一个区域,应该把相邻正方形共享边的两个顶点union起来。比如下图中,第一列的两个正方形,蓝色的两条边应该union,即左上角正方形的2号节点应该和左下角正方形的0号节点union;同理,第一行的两个正方形,红色的两条边也应该union,即左上角的1号节点和右上角的3号节点union。
其实,红色的边也可以union 0和2,但此时蓝色的边就应该union 1和3了,只要两者不一致并在整个程序中统一就行。

0-----1  0-----1
|     |  |     |
|     |  |     |
3-----2  3-----2
0-----1
|     |
|     |
3-----2

注意,不是把红色边的0和1 union,2和3 union,因为0和1可能属于不同的区域,比如下图中,红色的0和1就属于不同的区域了。

0-----1  0-----1
|   / |  | \   |
| /   |  |   \ |
3-----2  3-----2
0-----1
|     |
|     |
3-----2

初始化完成之后,就需要进行并查集操作了。如果遇到空格,好说,把这个正方形的四个顶点都union起来。
如果遇到左斜杠/,类似于上图左上角的分隔线,则把这个正方形中的四个顶点分成了两个不同的区域。此时,我们需要统一一个划分顶点的规则:被分隔的对角点和其顺时针的下一个顶点属于一个集合。比如3顺时针的下一个顶点是0,所以3和0 union;1顺时针的下一个顶点是2,所以1和2 union。
类似的,如果遇到右斜杠\,类似上图右上角的分隔线。根据统一的规则,0和1 union,2和3 union。
所有操作完成之后,统计一下并查集中不同区域的个数就是最终结果。
代码如下,注意%c会读取换行符,所以在每行开头先%c读取上一行的换行符。

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<algorithm>
#include<functional>
#include<vector>
using namespace std;
const int MAXN = 105;
int n, m;
vector<int> par(MAXN * MAXN * 4);
int find_par(int u) {
	if (par[u] != u)
		par[u] = find_par(par[u]);
	return par[u];
}
void union_par(int u, int v) {
	par[find_par(u)] = find_par(v);
}
int id(int x, int y, int z) {
	return x * m * 4 + y * 4 + z;
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	int total = n * m * 4;
	for (int i = 0; i < total; ++i)par[i] = i;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i > 0)union_par(id(i, j, 0), id(i - 1, j, 2));
			if (j > 0)union_par(id(i, j, 3), id(i, j - 1, 1));
			//if (i < n - 1)union_par(id(i, j, 2), id(i + 1, j, 0)); // 多余
			//if (j < m - 1)union_par(id(i, j, 1), id(i, j + 1, 3)); // 多余
		}
	}
	char c;
	for (int i = 0; i < n; ++i) {
		scanf("%c", &c); // 读取上一行的\n
		for (int j = 0; j < m; ++j) {
			scanf("%c", &c);
			if (c == ' ') {
				union_par(id(i, j, 0), id(i, j, 1));
				union_par(id(i, j, 1), id(i, j, 2));
				union_par(id(i, j, 2), id(i, j, 3));
				//union_par(id(i, j, 3), id(i, j, 0)); // 多余
			}
			else if (c == '/') {
				union_par(id(i, j, 3), id(i, j, 0));
				union_par(id(i, j, 1), id(i, j, 2));
			}
			else if (c == '\\') {
				union_par(id(i, j, 0), id(i, j, 1));
				union_par(id(i, j, 2), id(i, j, 3));
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < total; ++i) {
		if (find_par(i) == i)++ans;
	}
	printf("%d\n", ans);
	return 0;
}

本代码提交AC,用时4MS。

hihoCoder 1487-岛屿3

hihoCoder 1487-岛屿3

#1487 : 岛屿3

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

H国正在进行一项持续N周的填海造岛工程。整片工程海域可以被看作是1000x1000的网格。
每周都有一块1x1的单位方格海域被填成陆地。如果我们将连成一片的陆地(一块单位方格与它上下左右4个单位方格是相连的)视为岛屿,H国想监测每周末整片海域中一共存在有多少个岛屿,以及这些岛屿的总面积和总周长各是多少。
假设工程持续三周,第一周被填的海域坐标是(0, 0),那么第一周结束后有1座岛屿、总面积是1、总周长是4:

#..
...
...

第二周被填的海域坐标是(1, 1),那么第二周结束后有2座岛屿、总面积是2、总周长是8:

#..
.#.
...

第三周被填的海域坐标是(1, 0),那么第三周结束后有1座岛屿、总面积是3、总周长是8:

#..
##.
...

你能完成这项任务么?

输入

第一行包含一个整数N,表示工程持续的周数。(1 <= N <= 100000)
以下N行每行包含两个整数x和y,表示当周被填的海域坐标。(0 <= x, y < 1000)

输出

输出N行,每行包含3个整数,依次是当周末岛屿的数量、总面积和总周长。

样例输入
3
0 0
1 1
1 0
样例输出
1 1 4
2 2 8
1 3 8

有一个1000*1000的海域,每周往其中填入1*1的陆地,要求输出每周该海域中会形成多少个岛屿,以及岛屿的总面积和总周长。
其实这题不算难,只是太久没用并查集,用了DFS导致超时了。现在分别介绍两种方法。
首先我们来解决总面积和总周长这两个问题。
总面积好说,每周填入一个单元的陆地,则面积加一。
总周长要稍微注意,如果新加入的方块和其他所有方块都不邻接,则贡献+4周长;如果和一个已有方块邻接,则贡献+4-2周长;如果和两个已有方块邻接,则贡献+4-2*2周长;如果和3个已有方块邻接,则贡献+4-2*3周长。。。所以每加入一个方块,就看看该方块四周,如果和intercnt个方块邻接,则贡献周长+4-2*intercnt。
最麻烦的是求岛屿个数。当然可以像往常一样,对所有点DFS,求连通分量,但是TLE。
我稍微优化了一下,在board中,把每个连通分量都标记为一个不同的islandID,每次新加入一个方块时,令board[x][y]=++islandID,并从这个方块开始DFS,把所有和(x,y)连通的方块的ID都标记为新的(x,y)的islandID,同时记录一下被(x,y) DFS的方块旧的islandID。通过这个过程,能知道新方块(x,y)和多少个不同的旧岛屿相连,同时把所有和(x,y)相连的旧岛屿都标记为新的islandID了。
假设原来有n个岛屿,和新方块相连的旧岛屿有m个,则加入新方块之后,岛屿数更新为n-m+1,即m个旧岛屿都缩成1个新岛屿了。
DFS思路的代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdio>
#include<unordered_set>
using namespace std;
vector<vector<int>> board(1000, vector<int>(1000, 0));
vector<pair<int,int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} };
void dfs(int x,int y, int islandID, unordered_set<int>& neighbor) {
	neighbor.insert(board[x][y]);
	board[x][y] = islandID;
	for (int i = 0; i < dirs.size(); ++i) {
		int newx = x + dirs[i].first, newy = y + dirs[i].second;
		if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] != 0 && board[newx][newy] != islandID)dfs(newx, newy, islandID, neighbor);
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	int N, x, y;
	int island = 0, area = 0, perimeter = 0;
	int islandID = 1;
	bool first = true;
	scanf("%d", &N);
	while (N--) {
		scanf("%d %d", &x, &y);
		board[x][y] = islandID;
		++area;
		if (first) {
			perimeter = 4;
			island = 1;
			first = false;
		}
		else {
			int intercnt = 0; // 邻接方块数
			for (int i = 0; i < dirs.size(); ++i) {
				int newx = x + dirs[i].first, newy = y + dirs[i].second;
				if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] != 0)++intercnt;
			}
			perimeter = perimeter + 4 - 2 * intercnt;
			if (intercnt == 0)++island;
			else {
				unordered_set<int> neighbor; // 邻接岛屿旧编号+新方块编号
				dfs(x, y, islandID, neighbor);
				island = island - neighbor.size() + 2; // 因为neighbor中包含新方块编号,所以这里要多加1
			}
		}
		++islandID;
		printf("%d %d %d\n", island, area, perimeter);
	}
	return 0;
}

本代码提交TLE,用时2792MS。
比赛结束之后,看了看AC的代码,用的全是并查集,没一个用DFS的。。。
好吧,那就改成并查集。求总面积和总周长的方法都一样,不同的是求岛屿个数。
我们用数组来实现并查集,把坐标(x,y)编码成x*1000+y便于存入一维数组。对于每个新加入的点u,在并查集中先用自己代表自己,represent[u]=u。然后环顾四周,把四周陆地所在岛屿的代表放到neighbor中并去重,这样就能得到新方块邻接的旧岛屿数,根据n-m+1算到新岛屿数。最后把邻接的旧岛屿和新方块u union起来。
代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdio>
#include<unordered_set>
using namespace std;
vector<vector<int>> board(1000, vector<int>(1000, 0));
vector<pair<int, int>> dirs = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
vector<int> represent(1000 * 1000, -1);
int find_rep(int u) {
	if (u == represent[u])return u;
	else {
		represent[u] = find_rep(represent[u]);
		return represent[u];
	}
}
void union_rep(int u, int v) {
	represent[find_rep(u)] = find_rep(v);
}
int main() {
	//freopen("input.txt", "r", stdin);
	int N, x, y, u;
	int island = 0, area = 0, perimeter = 0;
	bool first = true;
	scanf("%d", &N);
	while (N--) {
		scanf("%d %d", &x, &y);
		board[x][y] = 1;
		++area;
		u = x * 1000 + y;
		represent[u] = u;
		if (first) {
			perimeter = 4;
			island = 1;
			first = false;
		}
		else {
			int intercnt = 0; // 邻接方块数
			unordered_set<int> neighbor; // 邻接岛屿
			for (int i = 0; i < dirs.size(); ++i) {
				int newx = x + dirs[i].first, newy = y + dirs[i].second;
				if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] == 1) {
					++intercnt;
					neighbor.insert(find_rep(newx * 1000 + newy));
				}
			}
			for (auto it = neighbor.begin(); it != neighbor.end(); ++it)union_rep(u, *it);
			perimeter = perimeter + 4 - 2 * intercnt;
			island = island - neighbor.size() + 1;
		}
		printf("%d %d %d\n", island, area, perimeter);
	}
	return 0;
}

本代码提交AC,用时436MS,果然快了不少。

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算法

POJ 1386-Play on Words

POJ 1386-Play on Words
Play on Words
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 10039 Accepted: 3441
Description
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ``acm'' can be followed by the word ``motorola''. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.
Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".
Sample Input
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
Sample Output
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
Source
Central Europe 1999


给定一系列字符串,问能否将这些字符串依次首尾相连成一个长串,字符串a和b能够相连的条件就是a的最后一个字母和b的第一个字母相同。
这个题目很有意思,像小时候玩的扑克牌游戏“钓鱼”。我一开始想到的是方法是深度优先搜索DFS,在输入的时候将字符串按首字母不同分到不同的队列里面,然后枚举每一个字符串为第一个字符串,进行DFS,如果DFS结束之后遍历了所有字符串,则成功,否则失败。
用枚举+DFS的方法代码如下:

#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int M=26;
int n,used;
vector<vector<string> > s;
//vector<string> rs;//rs内字符串的先后顺序就是这个游戏的先后顺序
bool dfs(string last)
{
	//rs.push_back(last);//记录字符串
	used++;
	if(used==n)
		return true;
	else
	{
		int c=last[last.size()-1]-'a';
		int sz=s.size();
		for(int i=0;i<sz;i++)
		{
			if(dfs(s[i]))
				return true;
			else
				used--;//rs.pop_back();//回溯
		}
		return false;
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int t;
	string tmp;
	cin>>t;
	while(t--)
	{
		cin>>n;
		s.clear();
		s.resize(M);
		for(int i=0;i<n;i++)
		{
			cin>>tmp;
			s[tmp[0]-'a'].push_back(tmp);
		}
		bool success=false;
		for(int i=0;i<M;i++)
		{
			int sz=s[i].size();
			for(int j=0;j<sz;j++)
			{
				used=0;
				success=false;
				if(dfs(s[i][j]))
				{
					success=true;
					break;
				}
			}
			if(success)
				break;
		}
		if(success)
			cout<<"Ordering is possible."<<endl;
		else
			cout<<"The door cannot be opened."<<endl;
	}
	return 0;
}

这一版代码提交MLT,估计是DFS递归栈太深导致的,看来只能想其他办法了。
看了讨论后,发现大多数方法是欧拉路+并查集/DFS。我们先来复习一下欧拉路:
通过图(无向图或有向图)中所有边一次且仅一次,行遍图中所有顶点的通路称为欧拉通路,通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图(Euler Graph),具有欧拉通路而无欧拉回路的图称为半欧拉图。
根据定义,欧拉回路肯定是欧拉通路。相关定理有:
1.无向连通图G是欧拉图,当且仅当G不含奇数度结点(G的所有结点度数为偶数);
2.无向连通图G含有欧拉通路,当且仅当G有零个或两个奇数度的结点;
3.有向连通图D是欧拉图,当且仅当D的基图(即其无向图)为连通图且D中每个结点的入度=出度
4.有向连通图D含有欧拉通路,当且仅当D的基图(即其无向图)为连通图且D中除两个结点外,其余每个结点的入度=出度,且此两点满足deg-(u)-deg+(v)=±1。(起始点s的入度=出度-1,结束点t的出度=入度-1 或两个点的入度=出度)
5.一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环。
6.如果图G是欧拉图且 H = G - uv,则H有奇数个u,v-迹仅在最后访问v;同时,在这一序列的u,v-迹中,不是路径的迹的条数是偶数。(Todia[1973])
以上内容摘自百度百科·欧拉图;关于欧拉路,还可以参考这篇文章。对于本题,我们可以把一个单词的首尾字母看成图的一条边,比如增加"acm"这个单词,则在图上增加一条a->m的有向边。要使所有字符串组成一个首尾相连的长串,等价于在a~z这26个字符串为点构成的图中只存在一条欧拉通路。判断是否存在欧拉通路可以用上面的定理3和4;判断是否只有一条欧拉通路(也就是判断基图是否连通)就需要借助并查集或者DFS,如果用并查集,要保证所有有边的点属于同一个集合;如果用DFS,则从图的某个点出发能遍历到所有右边的点。我使用的是并查集。
理清思路之后就可以开始写代码了,欧拉路+并查集版本的代码如下:

#include<iostream>
#include<string>
using namespace std;
const int M=26;
int n;
int showed[M];//showed[i]表示点i出现过,也就是有边连在i点
int G[M][M];//图
int father[M];//并查集
int degree[M][2];//degree[i][0]入度;degree[i][1]出度
void init_data()
{
	for(int i=0;i<M;i++)
	{
		father[i]=i;
		showed[i]=0;
		degree[i][0]=0;
		degree[i][1]=0;
		for(int j=0;j<M;j++)
			G[i][j]=0;
	}
}
int find_father(int x)
{
	return x==father[x]?x:(father[x]=find_father(father[x]));
}
void union_father(int x,int y)
{
	father[find_father(x)]=find_father(y);
}
//判断有边的点是否属于一个集合
bool is_one_set()
{
	int root=-1;
	for(int i=0;i<M;i++)
	{
		if(showed[i]==1)//有边
		{
			int tmp=find_father(i);
			if(root==-1)
				root=tmp;
			else if(tmp!=root)
				return false;
		}
	}
	return true;
}
bool judge()
{
	if(!is_one_set())
		return false;
	else
	{
		for(int i=0;i<M;i++)
		{
			for(int j=0;j<M;j++)
			{
				if(G[i][j]!=0)
				{
					degree[i][1]+=G[i][j];
					degree[j][0]+=G[i][j];
				}
			}
		}
		int a=0,b=0;//a:入度-出度=-1的个数;b:入度-出度=1的个数
		for(int i=0;i<M;i++)
		{
			int rs=degree[i][0]-degree[i][1];
			if(rs==-1)
				a++;
			else if(rs==1)
				b++;
			else if(rs!=0)
				return false;
		}
		if((a==1&&b==1)||(a==0&&b==0))//欧拉回路或欧拉通路
			return true;
		return false;
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int t,a,b;
	string tmp;
	cin>>t;
	while(t--)
	{
		cin>>n;
		init_data();
		for(int i=0;i<n;i++)
		{
			cin>>tmp;
			a=tmp[0]-'a';
			b=tmp[tmp.size()-1]-'a';
			showed[a]=1;
			showed[b]=1;
			G[a][b]++;//首字母指向尾字母的边
			union_father(a,b);//首字母指向尾字母的边
		}
		if(judge())
			cout<<"Ordering is possible."<<endl;
		else
			cout<<"The door cannot be opened."<<endl;
	}
	return 0;
}

本代码提交AC,用时782MS,内存244K。

hihoCoder 1067-最近公共祖先·二

hihoCoder 1067-最近公共祖先·二
#1067 : 最近公共祖先·二
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
上上回说到,小Hi和小Ho用非常拙劣——或者说粗糙的手段山寨出了一个神奇的网站,这个网站可以计算出某两个人的所有共同祖先中辈分最低的一个是谁。远在美国的他们利用了一些奇妙的技术获得了国内许多人的相关信息,并且搭建了一个小小的网站来应付来自四面八方的请求。
但正如我们所能想象到的……这样一个简单的算法并不能支撑住非常大的访问量,所以摆在小Hi和小Ho面前的无非两种选择:
其一是购买更为昂贵的服务器,通过提高计算机性能的方式来满足需求——但小Hi和小Ho并没有那么多的钱;其二则是改进他们的算法,通过提高计算机性能的利用率来满足需求——这个主意似乎听起来更加靠谱。
于是为了他们第一个在线产品的顺利运作,小Hi决定对小Ho进行紧急训练——好好的修改一番他们的算法。
而为了更好的向小Ho讲述这个问题,小Hi将这个问题抽象成了这个样子:假设现小Ho现在知道了N对父子关系——父亲和儿子的名字,并且这N对父子关系中涉及的所有人都拥有一个共同的祖先(这个祖先出现在这N对父子关系中),他需要对于小Hi的若干次提问——每次提问为两个人的名字(这两个人的名字在之前的父子关系中出现过),告诉小Hi这两个人的所有共同祖先中辈分最低的一个是谁?
提示一:老老实实分情况讨论就不会出错的啦!
提示二:并查集其实长得很像一棵树你们不觉得么?
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2~N+1行,每行分别描述一对父子关系,其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i,分别表示父亲的名字和儿子的名字。
每组测试数据的第N+2行为一个整数M,表示小Hi总共询问的次数。
每组测试数据的第N+3~N+M+2行,每行分别描述一个询问,其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i,分别表示小Hi询问中的两个名字。
对于100%的数据,满足N<=10^5,M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),所有询问中出现过的名字均在之前所描述的N对父子关系中出现过,第一个出现的名字所确定的人是其他所有人的公共祖先。
输出
对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:他们的所有共同祖先中辈分最低的一个人的名字。
样例输入
4
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
3
Sam Sam
Adam Sam
Micheal Kevin
样例输出
Sam
Adam
Adam


hihoCoder确实是个练习算法的好网站,之前我们写过朴素的最近公共祖先问题:hihoCoder Problem 1062: 最近公共祖先·一,但那是一个效率比较低的方法,这一次,hihoCoder详细给我们介绍了最近公共祖先的离线算法,而且讲解非常详细。
网站上的讲解详细,易于理解,我这里简单概括一下。所谓离线算法就是先把询问搜集起来,如果某个询问能先回答,则记录答案,直到把所有询问都解答了;与之相对的是在线算法,也就是每提出一个询问,我都要实时的马上回答。
离线算法综合了DFS和并查集。给定一个族谱(树形结构),我们先把每一个节点染成白色,并且在初始并查集中,每个点都是一个独立的集合,然后从树根开始深度优先遍历,当第一次经过某个节点a的时候,把它由白色改为灰色;如果第二次访问该节点的时候(也就是离开该点的时候),则把它由灰色改为黑色。
当a每次由白变灰之后,查看询问中是否出现过该节点,如果出现了,则查看询问中另一个节点b的颜色,如果b是灰色,则<a,b>的最近公共祖先就是b,因为b是灰色的,所以访问a之前肯定访问了b,所以它们的最近公共祖先是b;如果b是黑色,此时已经离开b了,并不能直接说明a和b的关系,但是<a,b>的最近公共祖先肯定在灰色链上,所以我们只要找出b向上的第一个灰色节点,就是<a,b>的最近公共祖先;如果b是白色,则说明b还没有访问,没有关于b的信息,所以我们暂时不管这个询问,等到访问到b时,a肯定不是白色,这是可以依据前两条规则得出它们的最近公共祖先。
当a每次由灰变黑之后,我们需要在并查集中将a和a的直接父节点合并UNION,因为当a由灰变黑时,a及其子树都访问结束了,但是a的直接父节点还没有访问结束,也就是说a的直接父节点还是灰色的,这样我们就记录了a向上的第一个灰色节点,这为上面的第二种情况判断做准备。
最近公共祖先的离线算法概括起来就是上面的内容,简单易懂也很强大。但是因为算法既包含DFS,又包含并查集,对初学者来说有一定的难度,而且这个题给出的数据是字符串形式的,数据量又很大,有很多细节需要注意。
我先把完整的代码贴出来,然后讲一下主要过程。

#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
const int MAX_N=100010;//最大人数
map<string,int> name_index;//名字转换为数字
vector<string> index_name(MAX_N);//数字转换为名字
int color[MAX_N]={0};//0:白;1:灰;2:黑,初始颜色都是白色
int s_f[MAX_N];//son_father。s_f[i]表示第i个儿子的直接父亲
vector<vector<int> > f_s(MAX_N);//f_s[i]表示第i个父亲的所有孩子
vector<vector<int> > show_at(MAX_N);//show_at[i]表示第i个人在哪些询问里出现过
int q_l[MAX_N];//第i个询问的左边
int q_r[MAX_N];//第i个询问的右边
int father[MAX_N];//用于并查集,和s_f不一样
vector<string> ans;//最终结果
//保存某个人的信息,并返回其下标
int store_name(string name)
{
     map<string,int>::iterator it=name_index.find(name);
     if(it==name_index.end())//还不存在
     {
          int curr_index=name_index.size();//用当前已有人数作为其下标,正好是递增的。
          name_index.insert(make_pair(name,curr_index));
          index_name[curr_index]=name;//记录
          father[curr_index]=curr_index;//初始的时候,并查集中每个元素都是一个独立的集合
          return curr_index;//返回下标
     }
     else
          return it->second;//已经存在,直接返回
}
//并查集FIND操作
int find_father(int name)
{
     return name==father[name]?name:(father[name]=find_father(father[name]));
}
//并查集UNION操作
void union_father(int name1,int name2)
{
     father[find_father(name1)]=find_father(name2);
}
//深度遍历族谱树
void DFS(int root)
{
     color[root]=1;//首先修改颜色为灰色
     int show_time=show_at[root].size();//查看该元素是否在询问里出现
     if(show_time!=0)
     {
          for(int i=0;i<show_time;i++)//判断所有询问
          {
               int column=show_at[root][i];
               int left=q_l[column];//找到该询问的左右元素
               int right=q_r[column];
               if(left==right)//如果是左右相同,则该自身即是其最近公共祖先
                    ans[column]=index_name[left];
               else
               {
                    if(left==root)//判断当前访问的是左边的还是右边的
                    {
                         if(color[right]==1)//另一个点为灰色
                              ans[column]=index_name[right];//结果即为该灰色点
                         else if(color[right]=2)//另一个点为黑色
                              ans[column]=index_name[find_father(right)];//找其向上最近的灰色节点
                    }
                    else
                    {
                         if(color[left]==1)//另一个点为灰色
                              ans[column]=index_name[left];
                         else if(color[left]=2)//另一个点为黑色
                              ans[column]=index_name[find_father(left)];
                    }
               }
          }
     }
     int sons=f_s[root].size();//查看是否有孩子节点
     if(sons!=0)
     {
          for(int i=0;i<sons;i++)
               DFS(f_s[root][i]);//深度遍历其所有孩子
     }
     color[root]=2;//改颜色为黑色
     union_father(root,s_f[root]);//和直接父节点UNION
}
int main()
{
     ios_base::sync_with_stdio(false);//取消同步,加速
     cin.tie(0);
     //freopen("input.txt","r",stdin);
     int n,m;
     string name1,name2;
     int index1,index2;
     cin>>n;
     while(n--)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          f_s[index1].push_back(index2);
          s_f[index2]=index1;
     }
     cin>>m;
     ans.resize(m);
     for(int i=0;i<m;i++)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          q_l[i]=index1;
          q_r[i]=index2;
          show_at[index1].push_back(i);
          show_at[index2].push_back(i);
     }
     DFS(0);
     for(int i=0;i<m;i++)
          cout<<ans[i]<<endl;
     return 0;
}

摆在我们面前的第一个问题就是数据的输入问题,题目给的每个人名都是字符串,当然我们可以直接用字符串构建一个树结构,然后进行查找、比较、赋值等操作,但是这样的时空效率都比较低,所以我们可以先用map<string,int> name_index和vector<string> index_name来记录人名字符串和人名数字下标,这样我们在DFS+并查集的时候可以只使用数字下标,到最后输出的时候再转换为字符串,提高效率。记录并返回人名数字下标的操作在函数int store_name(string name);中。
我们还需要记录父子关系,因为一个父亲可以有多个孩子,所以父亲-孩子关系需要用二维数组vector<vector<int> > f_s(MAX_N);来表示;而一个孩子只可能有一个父亲,所以孩子-父亲关系可以用一维数组int s_f[MAX_N];来表示。
还有两个数组需要初始化,每个节点的颜色初始化为白色,在并查集中每个节点单独为一个集合。
然后就是存储询问了。正如前面对LCA离线算法的描述,每当一个节点从白色变为灰色时,我们都要查看询问中是否出现过该节点。输入的询问中有很多节点,怎样来快速判断所有询问中是否有某个节点以及该询问中的另一个节点呢?如果这个问题处理不好,很可能就是TLE,反正我前两个版本都是因为这个原因TLE的。
这个问题可以通过两个步骤来解决,都是用空间来换时间。因为每一个询问都是由左右两个人名组成的,那么我们先把每次询问的左右两个人名记录在int q_l[MAX_N];和int q_r[MAX_N];中。然后还用一个二维数组vector<vector<int> > show_at(MAX_N);来记录某一个节点在哪些询问里出现过。这样当我们DFS到某个节点a时,首先查看show_at[a]这个数组是否为空,如果为空,说明a没有出现在任何一次询问中;如果不为空,则show_at[a]记录了a出现的所有询问的序号,根据这个序号,我们再去查q_l和q_r,这样就可以取出a出现时的那个询问的左右两个人名是什么了。所以整个过程只需要O(1)的时间,大大提高了时间效率。
因为题目中说明了

第一个出现的名字所确定的人是其他所有人的公共祖先。

所以我们以第一个人名下标0来DFS树结构。DFS的过程和上面的算法描述一致,我这里就不多说了,代码中都有详细的注释。
还有一个小问题需要注意,因为编译器不一样,在用vector声明二维数组的时候,我在VS2010下可以这样:

vector<vector<int>> a; //sth

但是提交之后会报Compile Error的错误:error: ‘>>’ should be ‘> >’ within a nested template argument list,也就是说这个编译器把>>看成了移位操作符,所以我们在两个箭头之间加一个空格> >这样就没问题了。
我上面的代码版本提交后AC,用时711MS,内存30MB。这是我迄今为止内存消耗最大的一次AC。
总的来说,这个题是好题,很考验选手的综合能力,特别是本题用到的各种数据结构较多,需要全盘考虑,不断优化。

hihoCoder 1066-无间道之并查集

hihoCoder 1066-无间道之并查集
#1066 : 无间道之并查集
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
这天天气晴朗、阳光明媚、鸟语花香,空气中弥漫着春天的气息……额,说远了,总之,小Hi和小Ho决定趁着这朗朗春光出去玩。
但是刚刚离开居住的宾馆不久,抄近道不小心走入了一条偏僻小道的小Hi和小Ho就发现自己的前方走来了几个彪形大汉,定睛一看还都是地地道道的黑人兄弟!小Hi和小Ho这下就慌了神,捡肥皂事小,这一身百把来斤别一不小心葬身他乡可就没处说去了。
就在两人正举足无措之时,为首的黑叔叔从怀里掏出了一件东西——两张花花绿绿的纸,分别递给了小Hi和小Ho。
小Hi和小Ho接过来,只见上面写道(译为中文):“本地最大的帮派——青龙帮,诚邀您的加入!”下面还详细的列出了加入青龙帮的种种好处。
于是两人略感心安,在同黑叔叔们交谈一番之后,已是均感相见恨晚。同时,在小Hi和小Ho表示自己不日便将回国之后,黑叔叔们也没有再提加入帮派之事,但是那为首的黑叔叔思索一会,开口道(译为中文):“我现在有一个难题,思索了很久也没法子解决,既然你们俩都是高材生,不如来帮我看看。”
小Hi和小Ho点了点头表示没问题,于是黑叔叔继续说道:“这个问题是这样的,我们帮派最近混进了许多警察的卧底,但是在我们的调查过程中只能够知道诸如‘某人和另一个人是同阵营的’这样的信息,虽然没有办法知道他们具体是哪个阵营的,但是这样的信息也是很重要的,因为我们经常会想要知道某两个人究竟是不是同一阵营的。”
小Hi和小Ho赞同的点了点头,毕竟无间道也都是他们看过的。
黑叔叔接着说道:“于是现在问题就来了,我希望你们能写出这样一个程序,我会有两种操作,一种是告诉它哪两个人是同一阵营的,而另一种是询问某两个人是不是同一阵营的……既然你们就要回国了,不如现在就去我们帮派的总部写好这个程序再走把。”
为了生命安全与……小Hi和小Ho都不得不解决这个问题!那么他们究竟从何下手呢?
提示:说起来其实就是不断的合并集合嘛~
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,表示黑叔叔总共进行的操作次数。
每组测试数据的第2~N+1行,每行分别描述黑叔叔的一次操作,其中第i+1行为一个整数op_i和两个由大小写字母组成的字符串Name1_i, Name2_i,其中op_i只可能为0或1,当op_i=0时,表示黑叔叔判定Name1_i和Name2_i是同一阵营的,当op_i=1时,表示黑叔叔希望知道Name1_i和Name2_i是否为同一阵营的。
对于100%的数据,满足N<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),对于所有的i,满足Name1_i和Name2_i是不同的两个人。
输出
对于每组测试数据,对于黑叔叔每次op_i=1的操作,输出一行,表示查询的结果:如果根据已知信息(即这次操作之前的所有op_i=0的操作),可以判定询问中的两个人是同一阵营的,则输出yes,否则输出no。
样例输入
10
0 Steven David
0 Lcch Dzx
1 Lcch Dzx
1 David Dzx
0 Lcch David
0 Frank Dzx
1 Steven Dzx
1 Frank David
0 Steven Dzx
0 Dzx Frank
样例输出
yes
no
yes
yes


这是一道考察并查集的好题目。并查集也叫做不相交集。它主要有两个操作:FIND和UNION。
假设有两个不相交集分别为A,B,用各自集合内的元素a和b分别代表A和B,也就是说A中所有元素(包括a自己)的祖先都是a,B中所有元素(包括b自己)的祖先都是b。FIND操作就是给定一个元素c,要找到它的祖先。常规思路就是递归的顺着族谱往上找,但是为了后续查找的高效,可以路径压缩一下,也就是把查找过程中的节点的祖先都赋为c的祖先,这样下次查找其他元素的祖先时就快得多。
UNION操作就是已知元素c和d,要把这两个元素所在的集合合并起来,自然就是先用FIND找到c和d的祖先,然后把其中一个祖先当做另一个祖先的祖先,这样就把两个集合合并起来了。
至于这道题,题目中的提示已经把并查集的FIND函数写出来了。

如果op_i=0,说明这两个人是同一个集合的,即他们有共同的祖先,则首先判断这两个人在不在map中,如果不在,则以自身为祖先加入到map中,然后执行UNION操作把他们合并为一个集合。
如果op_i=1,要判断两个人是否在一个集合中,想当然的FIND他们的祖先,如果祖先相同,说明他们是一个集合的。
理清了上述关系,马上写出代码:

#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,string> represent;
//并查集FIND操作
string find_represent(string name)
{
     if(name==represent[name])
          return name;
     else
     {
          represent[name]=find_represent(represent[name]);//把经过的节点全部链接到根节点
          return represent[name];
     }
}
int main()
{
      //freopen("input.txt","r",stdin);
     int n;
     int op;
     string name1,name2;
     cin>>n;
     while(n--)
     {
          cin>>op>>name1>>name2;
          if(op==0)
          {
               if(represent.find(name1)==represent.end())
                    represent[name1]=name1;
               if(represent.find(name2)==represent.end())
                    represent[name2]=name2;
               represent[find_represent(name1)]=find_represent(name2);//UNION操作
          }
          else
          {
               //**********也需要先判断是否在map里*********
               if(represent.find(name1)==represent.end())
                    represent[name1]=name1;
               if(represent.find(name2)==represent.end())
                    represent[name2]=name2;
               //******************************************
               if(find_represent(name1)==find_represent(name2))
                    cout<<"yes"<<endl;
               else
                    cout<<"no"<<endl;
          }
     }
     return 0;
}

本代码提交AC,用时243MS,内存1MB。
需要注意的是,由于本题使用MAP实现,在执行FIND操作时有这么一句:

if(name==represent[name])

对于STL的map,如果本来map中不存在a这个元素,执行了if(map[a]=="sth")之后,也会自动把a加入map,最后就是map[a]="",为空。虽然就某一次来说,这样判断的结果和下面修正的结果是一样的,但是如果下一次op_i=0需要加入a时发现map中已经有a了,就直接执行UNION操作了,但是这个时候a的祖先却是空"",而本来a的祖先应该是它自己a的。所以这就会对后面的结果产生影响。所以当我们op_i=1时,如果某个人不在map中,我们也要把它加入map并使其祖先为自身。
关于这道题,这篇题解写得还可以,它把并查集的UNION和FIND分开来写,条理清晰,值得参考,不过它没有路径压缩。
之前一直对并查集心存恐惧,刷过这道题之后,发现并查集也就这么回事,代码简洁,也不难理解。继续坚持!