POJ 1988相对偏移

//不容易啊，终于自己a了一道这种类型的题

//

#include<stdio.h>

#include<iostream>

using namespace std;

const int N=30010;

struct node {

int front,last,count;

}pre[N];

int find(int x) {//指向队尾

if(x!=pre[x].last) {

int h=pre[x].last;

pre[x].last=find(pre[x].last);

pre[x].count=pre[h].count+pre[x].count;//路径压缩

}

return pre[x].last;

}

int find1(int x) {//求队首相当于一个元素指向两个方向，这个指向队首

if(x!=pre[x].front)

pre[x].front=find1(pre[x].front);

return pre[x].front;

}

int main() {

int n,i,a,b,f1,f2;

char s[2];

while(scanf("%d",&n)!=EOF) {

for(i=1;i<=N;i++) {

pre[i].last=i;

pre[i].front=i;

pre[i].count=0;

}

while(n--) {

scanf("%s",s);

if(s[0]=='M') {

scanf("%d%d",&a,&b);

f1=find(a);//a集合的队尾

f2=find(b);

if(f1==f2)//如果有相同的根节点不用再加了

continue;

f2=find1(b);//求b集合的队首

pre[f1].last=f2;//a集合队尾指向b集合队首

pre[f1].count=1;//权值为1

pre[f2].front=f1;//b集合的队首指向a集合的队尾

}

else {

scanf("%d",&a);

find(a);

printf("%d\n",pre[a].count);

}

}

}

return 0;

}

//我在网上看了个代码我承认我的方法没有人家的好我又写了一下

#include<stdio.h>

#include<iostream>

using namespace std;

const int N=30010;

int pre[N],dis[N],sondis[N];

int find(int x) {

if(x!=pre[x]) {

  int h=pre[x];

  pre[x]=find(pre[x]);

  dis[x]+=dis[h];

}return pre[x];

}

void unions(int x,int y) {

int f1=find(x);

int f2=find(y);

if(f1==f2)

  return ;

pre[f1]=f2;

dis[f1]=sondis[f2]+1;

sondis[f2]=sondis[f2]+sondis[f1]+1;

}

int main() {

int n,m,i,j,k,a,b;

char s[2];

while(scanf("%d",&n)!=EOF) {

  for(i=1;i<=N;i++) {

   pre[i]=i;

   dis[i]=0;

   sondis[i]=0;

  }

  while(n--) {

   scanf("%s",s);

   if(s[0]=='M') {

    scanf("%d%d",&a,&b);

    unions(a,b);

   }

   else {

    scanf("%d",&a);

    find(a);

    printf("%d\n",dis[a]);

   }

  }

}

return 0;

}

巴特西

POJ 1988相对偏移

最新文章

热门文章