啥网站都能看的浏览器/什么叫关键词举例

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1213

解题思路：并查集裸题。

并查集两大功能：①合并两个集合②查找某个元素在哪个集合

若并查集数组为uf[]，则uf[i]表示编号为i的点的“上级”，如果uf[i] = i表示当前的点是一个集合的“大头目”。

int find1(int x)///找到大头目
{int r = x;while (r!=uf[r]) r = uf[r];return r;
}void join(int a,int b)///合并两个集合
{int c = find1(a),d = find1(b);if (c!=d) uf[c] = d;
}

不过直接这样找大头目太慢，所以有了路径压缩。也就是每次查找的时候把当前查找点和找到大头目路上的各种上级，上级的上级，上级的上级的上级这种全部直接并到大头目下。形象来说，原先这条逐渐向上层汇报的路上的人，现在全部变成了大头目的直系下属。

int find1(int x)
{int r = x;while (r!=uf[r]) r = uf[r];for (int i=x,j;i!=r;i=j){j = uf[i];uf[i] = r;}return r;
}

回到这题，把所有关系用并查集维护后，统计有多少个大头目即可（大头目即uf[i]=i）。

代码：

#include<cstdio>
#include<cstring>const int N = 1e3+5;int uf[N];int find1(int x)
{int r = x;while (r!=uf[r]) r = uf[r];for (int i=x,j;i!=r;i=j){j = uf[i];uf[i] = r;}return r;
}void join(int a,int b)
{int c = find1(a),d = find1(b);if (c!=d) uf[c] = d;
}int main()
{int t;scanf("%d",&t);while (t--){int n,m;scanf("%d %d",&n,&m);for (int i=1;i<=n;i++) uf[i] = i;while (m--){int a,b;scanf("%d %d",&a,&b);join(a,b);}int ans = 0;for (int i=1;i<=n;i++) if (uf[i] == i) ans++;printf("%d\n",ans);}return 0;
}