数据结构MOOC
PTA习题
这道题考察并查集的操作，合并以及找根结点
机翻：
1、条件准备
node是数组存放1-N结点的根节点的，n为总结点数
#include <iostream>
using namespace std;const int N = 1e4 + 5;
int node[N];
int n;先初始化，每一个结点的根节点是本身。
然后循环输入每一组数据，遇到S就退出。
遇到I就将两个结点插入到一棵树中，用insert函数实现
遇到C就检查两个结点是否在同一棵树中，用check实现o
最后跳出循环，看看一共有几棵树，并输出对应语句，用component函数实现
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++)node[i] = i;while (1){char c;cin >> c;if (c == 'S')break;int a, b;cin >> a >> b;if (c == 'I')insert(a, b);else if (c == 'C')check(a, b);}component();return 0;
}2、find函数
该函数是找结点所在树的根节点。如果下标与值相等，则它自己就是根节点。
否则沿着路径找其对应根节点，并更新该结点的祖宗结点为返回的根节点
这个操作保证每次find查找完，所遍历的结点它们的每个结点的祖宗结点都更新了
int find(int a)
{if (node[a] == a)return a;elsereturn node[a] = find(node[a]);//路径压缩
}3、insert函数
将两个结点所在树合并，先找到它们对应的祖宗结点。
这里采用值大的作为新的根节点，并把另一个祖宗结点的值改为新的根节点。
void insert(int a, int b)
{int parenta = find(a), parentb = find(b);if (parenta > parentb)node[parentb] = parenta;elsenode[parenta] = parentb;
}4、check函数
看看两个结点祖宗结点是否一样，输出对应数据
void check(int a, int b)
{if (find(a) == find(b))cout << "yes" << endl;elsecout << "no" << endl;
}5、component函数
找一共有多少棵树，只需遍历一遍每个结点，若值为其下标，则它就为这棵树的根节点。
如果只有一棵树，那么所有结点都连起来了，否则输出有多少棵树
void component()
{int num = 0;for (int i = 1; i <= n; i++)if (i == node[i])num++;if (num == 1)cout << "The network is connected.";elsecout << "There are " << num << " components.";
}6、总结
这道题运用了并查集的知识，难度不算大，没有用到结构体、指针，较好理解。
完整代码如下：
#include <iostream>
using namespace std;const int N = 1e4 + 5;
int node[N];
int n;int find(int a)
{if (node[a] == a)return a;elsereturn node[a] = find(node[a]);
}void insert(int a, int b)
{int parenta = find(a), parentb = find(b);if (parenta > parentb)node[parentb] = parenta;elsenode[parenta] = parentb;
}void check(int a, int b)
{if (find(a) == find(b))cout << "yes" << endl;elsecout << "no" << endl;
}void component()
{int num = 0;for (int i = 1; i <= n; i++)if (i == node[i])num++;if (num == 1)cout << "The network is connected.";elsecout << "There are " << num << " components.";
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++)node[i] = i;while (1){char c;cin >> c;if (c == 'S')break;int a, b;cin >> a >> b;if (c == 'I')insert(a, b);else if (c == 'C')check(a, b);}component();return 0;
}附录：并查集相关操作
#define MAXN 1000
typedef int ElementType;
typedef int SetName;
typedef ElementType SetType[MAXN];void Union(SetType S,SetName root1,SetName root2)
{if(S[root2]<S[root1]){S[root2]+=S[root1];S[root1]=root2; }else {S[root1]+=S[root2];S[root1]=root2;}
}
SetName find(SetType S,ElementType x)
{if(S[x]<0)return x;else return S[x]=find(S,S[x]);
}
