冒泡 算法之美

样例输入
5 3 1
1 3
2 4
3 5
1 2
样例输出
No
样例解释
1,2不是亲戚

看到这道题，很多人一下子就懵了。卧槽这是什么鬼？然而我们细想一下，关系其实可以用一个邻接矩阵来存储。
邻接矩阵被描述为n*n的矩阵，其中a[x][y]表示x,y的关系。是亲戚为1,否则为0。这样，数据结构就明朗了。

上一道题的矩阵可以写成
0 0 1 0 0
0 0 0 1 0
1 0 0 0 1
0 1 0 0 0
0 0 1 0 0
特别说明，自己到自己的为0。

>>>解法一<<<
这道题很容易想到用动态规划来做，求出两两之间的距离。若为无穷大则说明不连通。我们用很大的整数9999999999表示无穷大，建立一个二维数组dis[][]
这一道题就可以看成
dis
0 ∞ 1 ∞ ∞
∞ 0 ∞ 1 ∞
1 ∞ 0 ∞ 1
∞ 1 ∞ 0 ∞
∞ ∞ 1 ∞ 0

用三重循环枚举每一个点作为中间点的情况，两点间的距离是否能被更新。代码很容易写出。
for (k=1; k<=n; k++)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
dis[i][j]=max(dis[i][j],dis[i][k]+dis[k][j])
//每一个k做中介

这样只要判断两点上距离是否小于设定的无穷大即可

这个算法的复杂度是O(n^3)，查找的复杂度O(ask)，总共O(n^3)。空间复杂度O(n^2)。时间和空间都不很好。因此我们来介绍第二种算法
>>>解法二<<<
稍微一想便知道，我们从某点出发只需要对这个矩阵进行一次遍历，就可以知道所有与他连通的点。其余的点就不连通。我们可以用简单的深度优先搜索来完成。

代码很好写，用递归进行深度优先搜索。
bool find[100000]={0}
//c++用memset清0
void dfs(int i){
find[i]=1;
for (int j=1; j<=n; j++){
if (!find[j]&&f[i][j])
dfs(j);
}
}

从ask的起点遍历，看终点是否find即可，时间复杂度O(ask*n*n)，空间不变(矩阵)

这样的时间复杂度仍然很高。我们需要寻求一种新方法。
>>>解法三<<<
我们可以运用集合的知识来解决。把有亲戚关系的人合并到一个集合，只需要判断两人是否在一个集合中，就可以得出他们的亲戚关系。但是集合怎么实现呢？

我们可以用并查集的方法来做。并查集，顾名思义就是可以合并-查找的集合。通常，我们用一个数组来实现。a[100000]。现将a[i]=0(1<=i<=n)，表示他们各自处在自己的集合中。遇到两个人p,q，就把a[p]=q，把他和他的所有元素指向q，也就是把它们合并成了一个集合。

查找时间复杂度O(lgn)，合并O(1)，提问O(lgn)，总共O(nlgn+asklgn)

尽管这样复杂度已经很优了，但针对特殊设计的数据，仍然有可能超时。例如当数据成链状时，查找最坏复杂度为O(n)，退化到O(n^2+ask*n)

我们考虑种优化方法，当合并两个集合的时候，并不是简单地将一个指向另一个，而是将它指向他另一个最终父结点，从而尽可能地避免链状结构。
long find(int x) {
if (a[x] == 0)
return x;
a[x] = find(a[x]);
return a[x];
}