# 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.

# hihoCoder 1495-矩形分割

hihoCoder 1495-矩形分割

### 描述

/\
\/


/\/\
\  /
\/\


### 输出

3 4
/\/\
\  /
\/\

7

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


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


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

# hihoCoder 1487-岛屿3

hihoCoder 1487-岛屿3

### 描述

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


#..
.#.
...


#..
##.
...


### 输出

3
0 0
1 1
1 0

1 1 4
2 2 8
1 3 8

# 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 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

# 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，又包含并查集，对初学者来说有一定的难度，而且这个题给出的数据是字符串形式的，数据量又很大，有很多细节需要注意。 我先把完整的代码贴出来，然后讲一下主要过程。 [cpp] #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; } [/cpp] 摆在我们面前的第一个问题就是数据的输入问题，题目给的每个人名都是字符串，当然我们可以直接用字符串构建一个树结构，然后进行查找、比较、赋值等操作，但是这样的时空效率都比较低，所以我们可以先用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)的时间，大大提高了时间效率。 因为题目中说明了

# 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