数据结构-北大-1703

[china_sjc]

源代码：
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

#define M 100001
struct Crime{
int parent,weight;
};
Crime crime[M]; // 所用数据结构
int n,m;

main( ){
int k,one,two;
char order;
// freopen("data.txt","r",stdin);
int kk,X;
scanf("%d",&X);
for(kk=0;kk<X;kk++){
memset(crime,0,sizeof(crime)); //初始化清零
scanf("%d%d",&n,&m);
for(k=0;k<m;k++){
while(1){ // 清除空格等额外字符，有点多虑
order=getchar();
if(order=='D'||order=='A') break;
}
scanf("%d%d",&one,&two);
if(order=='D'){ // 执行命令 D one two
int temp1=one,temp2=two,t1=0,t2=0;
while(crime[temp1].parent!=0) {
t1+=crime[temp1].weight;temp1=crime[temp1].parent;
}// 查找one 所在树的头节点，并计算到头节点的权之和
while(crime[temp2].parent!=0) {
t2+=crime[temp2].weight;temp2=crime[temp2].parent;
} // 查找 two 所在树的头节点，并计算到头节点的权之和

if(temp1!=temp2){
if(t1<t2){ // 若t1<t2 ,把 one 所在树挂到 two上
crime[temp1].parent=temp2;
crime[temp1].weight=(t1-t2+1)%2;
}
else { // 反之，将 two 所在树挂到 one 上。
crime[temp2].parent=temp1;
crime[temp2].weight=(t1-t2+1)%2;
}
}
}
else{ // 执行命令 A one two
int temp1=one,temp2=two,t1=0,t2=0;
while(crime[temp1].parent!=0) {
t1+=crime[temp1].weight;temp1=crime[temp1].parent;
} // 查找one 所在树的头节点，并计算到头节点的权之和
while(crime[temp2].parent!=0) {
t2+=crime[temp2].weight;temp2=crime[temp2].parent;
} // 查找 two 所在树的头节点，并计算到头节点的权之和
if(temp1!=temp2) // 不在同一棵树
printf("Not sure yet.\n");
else if((t2-t1)%2==0) // 权相差为偶数
printf("In the same gang.\n");
else // 权相差为一个奇数
printf("In different gangs.\n");
}
}
}
return 1;
}

[china_sjc]

时空分析：
时间复杂度：
最坏情形为O(m*n)，平均情况为O(mlogn)，后者是可以接受的。
空间复杂度：
用了一个大数组，为O(n)。

[china_sjc]

数据结构：
对于每个点需要保存两个信息，一个是其父节点，另一个则为它到其父节点那条边的权。所以我们用一个结构体来保存每个罪犯节点。
struct Crime{
int parent；// 父节点位置
int weight; // 权
};
然后用一个数组来表示100000个罪犯：
Crime crime[100001];//注意程序中罪犯编号从1开始。

[china_sjc]

解题思路：
题目的难点是怎样保存 D i j 这条信息。本质上就是把两个集合并起来，一个集合是现在已经知道的跟i相关的罪犯，另外一集合是现知的跟j相关的罪
犯，当然这两个集合有可能是同一个集合（此时i，j之间的关系在此信息之前就已经确定了）。这样所有的罪犯分成若干个集合，每个罪犯属于且仅属于一个集
合。对于每条信息D i j，我们都把包含i的集合和包含j的集合并成一个集合。
我们采取森林的方法来保存这些集合。对于属于同一颗树的所有节点，划分一个集合。这样两个集合之间的并就简化为了两棵树之间的合并了。
为了查询i所在的树，不断查找其父节点，最后找到i所在树的头节点即可。i,j在同一颗树上的充分必要条件就是他们的头节点一样。而D i j 即是将
一个头节点连到另外一个头节点上去（如图所示）。

至此为止，我们保存了对于任何i,j，他们是否相关（即是否可以判断是否在同一个帮派，其依据就是是否在同一颗树上）的信息。
我们还需要判断对于同一颗树上的i,j，他们是否属于同一个帮派。注意到上面我们的判断准则，对于树的一条边，需要保存两个端点是否在同一个帮派的信
息，称为权，比如用0表示是同一个帮派，反之用1表示。此时对于从i到j的一条路径，将所有边上的权相加，若为奇数则不在同一个帮派，反之则在同一个帮
派。
每一条边的权可以保存在下面那个端点的信息里面。
几个细节和注意事项：
1． 罪犯编号从1开始，方便起见，储存也从1开始。
2． 一开始要将所有父节点位置清零。
3． 最重要的一点是，需要充分发挥树的作用，不要使得成为一个链表。即需要使得树的层数尽量少，这样可以大大降低查找每个点所在树的头节点的时间复杂
度，比如说若为链表则为O(n),若为一个完全二叉树则为O(logn)。具体方法是对于i,j查找树的头节点的时候，记下它们到各自头节点的层数，然
后将层数少的那个树连到层数较多的那棵树上（如上图）。不过在我的程序中使用权作为层数来用的，也能过J。