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

```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();
}
};
```

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

```#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;
}
```

# hihoCoder 1487-岛屿3

hihoCoder 1487-岛屿3

### 描述

H国正在进行一项持续N周的填海造岛工程。整片工程海域可以被看作是1000x1000的网格。

```#..
...
...
```

```#..
.#.
...
```

```#..
##.
...
```

### 输出

```3
0 0
1 1
1 0```

```1 1 4
2 2 8
1 3 8```

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;
}
```

```#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;
}
```

# hihoCoder week 49-1-欧拉路·一

hihoCoder week 49-1-欧拉路·一 6 8
1 2
1 4
2 4
2 5
2 3
3 6
4 5
5 6

Full

```#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)
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;
}
```

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

```#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-'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;
}
```

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)

```#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];//degree[i]入度；degree[i]出度
void init_data()
{
for(int i=0;i<M;i++)
{
father[i]=i;
showed[i]=0;
degree[i]=0;
degree[i]=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]+=G[i][j];
degree[j]+=G[i][j];
}
}
}
int a=0,b=0;//a:入度-出度=-1的个数；b:入度-出度=1的个数
for(int i=0;i<M;i++)
{
int rs=degree[i]-degree[i];
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-'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;
}
```

# hihoCoder 1067-最近公共祖先·二

hihoCoder 1067-最近公共祖先·二
#1067 : 最近公共祖先·二

4
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
3
Sam Sam
Adam Sam
Micheal Kevin

Sam
Adam
Adam

hihoCoder确实是个练习算法的好网站，之前我们写过朴素的最近公共祖先问题：hihoCoder Problem 1062: 最近公共祖先·一，但那是一个效率比较低的方法，这一次，hihoCoder详细给我们介绍了最近公共祖先的离线算法，而且讲解非常详细。

```#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;
}
```

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

# hihoCoder 1066-无间道之并查集

hihoCoder 1066-无间道之并查集
#1066 : 无间道之并查集

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

UNION操作就是已知元素c和d，要把这两个元素所在的集合合并起来，自然就是先用FIND找到c和d的祖先，然后把其中一个祖先当做另一个祖先的祖先，这样就把两个集合合并起来了。 ```#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;
}
```

```if(name==represent[name])
```