#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define MAX_TREE_SIZE 100
typedef int Status; /* 函数结果状态代码,如OK等 */
typedef char TElemType;
typedef struct {
TElemType data;
int parent; /* 双亲位置域 */
} PTNode;
typedef struct {
PTNode nodes[MAX_TREE_SIZE+1];
int n; /* 结点数 */
} PTree;
typedef PTree MFSet;
int find_mfset(MFSet S, int i) { // 算法6.8
// 找集合S中i所在子集的根
int j;
if (i<1 || i>S.n) return -1; // i不是S中任一子集的成员
for (j=i; S.nodes[j].parent>0; j=S.nodes[j].parent);
return j;
}// find_mfset
Status merge_mfset(MFSet &S, int i, int j) { // 算法6.9
// S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj的根结点。
// 求并集Si∪Sj。
if (i<1 || i>S.n || j<1 || j>S.n) return ERROR;
S.nodes[i].parent = j;
return OK;
} // merge_mfset
Status mix_mfset(MFSet &S, int i, int j) { // 算法6.10
// S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj的根结点
// 求并集Si∪Sj。
if (i<1 || i>S.n || j<1 || j>S.n) return ERROR;
if (S.nodes[i].parent>S.nodes[j].parent) { // Si所含成员数比Sj少
S.nodes[j].parent+=S.nodes[i].parent;
S.nodes[i].parent=j;
} else { // Sj的元素比Si少
S.nodes[i].parent+=S.nodes[j].parent;
S.nodes[j].parent=i;
}
return OK;
} // mix_mfset
int fix_mfset(MFSet &S, int i) { // 算法6.11
// 确定i所在子集,并将从i至根路径上所有结点都变成根的孩子结点。
int j,k,t;
if (i<1 || i>S.n) return -1; // i 不是S中任一子集的成员
for (j=i; S.nodes[j].parent>0; j=S.nodes[j].parent);
for (k=i; k!=j; k=t) {
t=S.nodes[k].parent; S.nodes[k].parent=j;
}
return j;
} // fix_mfset
int main() {
int n,i,x,y,k;
MFSet Set;
scanf("%d%d", &n, &k);
Set.n = n;
for(i=1;i<=n;i++) {
Set.nodes[i].data=i;
Set.nodes[i].parent=-1;
} // 建立n个只有一个元素的集合
for(i=1;i<=k;i++) {
scanf("%d%d", &x, &y);
x = find_mfset(Set, x); // 找到子集的根节点
y = find_mfset(Set, y); // 找到子集的根节点
mix_mfset(Set, x, y);
fix_mfset(Set, x);
fix_mfset(Set, y);
}
scanf("%d%d", &x, &y);
x = find_mfset(Set, x); // 找到子集的根节点
y = find_mfset(Set, y); // 找到子集的根节点
if (x == y)
puts("YES");
else
puts("NO");
return 0;
}
/**************************************************************
Problem: 2156
User: admin
Language: C++
Result: Accepted
Time:9 ms
Memory:1144 kb
****************************************************************/