练习使用一下并查集模板（嵌在代码中），因为今天省赛热身赛用到了并查集的father[]或者说是per[]数组的思想（也可能不是啦）。感觉明天会有一道关于最短路或者最小生成树的题
hdu1232 click here
#include <cstdio> #define N 1007 int pre[N]; int find(int x) { //查找根节点 int r = x; while (pre[r] != r) //返回根节点 r r = pre[r]; int i = x, j; while (i != r) { //路径压缩 j = pre[i]; // 在改变上级之前用临时变量 j 记录下他的值 pre[i] = r; //把上级改为根节点 i = j; } return r; } void join(int x, int y) { //若x, y不连通，就把它们所在的连通分支合并起, int fx = find(x), fy = find(y); if (fx != fy) pre[fx] = fy; } int main() { int n, m; while(~scanf("%d", &n) && n) { scanf("%d", &m); for (int i = 0; i <= n; ++i) pre[i] = i; int x, y; while(m-- > 0) { scanf("%d%d", &x, &y); join(x, y); } int cnt = 0; for (int i = 1;i <= n; ++i) if (pre[i] == i) cnt++; printf("%d\n", --cnt); } return 0; }
