题解 | #连通图#

#include <stdio.h>
//思想：并查集
//拥有同一祖先father的顶点一定是联通的，起初将每个顶点的祖先都设为自己，之后每读入一条边x1，x2都将x2的最终祖先的祖先设为x1的祖先
//从逻辑上讲，也就是将以x2祖先为根节点的连接树，接到以x1祖先为根节点的树上，这样两边树上的节点都联通了
//最终通过判断每个节点的最终祖先是否一样，一样则联通
//技巧:在构建祖先树的过程中，可以在找祖先函数Find中，将树高压缩，每次对一个x进行找祖先时候，都将x的直接父亲=x的原始祖先，降低树的高度
//使得最终判断时间能够减少
int father[1001];
int Find(int x) { //找到最原始祖先
  if (x == father[x]) {
    return x;
  } else {
    father[x] = Find(father[x]);
    return father[x];
  }
}

int main() {
  int n, m;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (int i = 1; i <= n; i++) {
      father[i] = i;
    }

    int x1, x2;
    for (int i = 0; i < m; i++) { //记录边的点
      scanf("%d%d", &x1, &x2);
      father[Find(x2)] = Find(x1);

    }
    int tmp = Find(1);
    for (int i = 1; i <= n; i++) {
      if (Find(i) != tmp) {
        printf("NO\n");
        break;
      }
      if (i == n) {
        printf("YES\n");
      }
    }
  }
}