# 58 条题解

• @ 2018-02-15 14:38:11

#1 Accepted 6ms 772.0 KiB
#2 Accepted 5ms 2.875 MiB
#3 Accepted 9ms 892.0 KiB
#4 Accepted 14ms 996.0 KiB
#5 Accepted 46ms 1.273 MiB
#6 Accepted 69ms 1.945 MiB
#7 Accepted 145ms 4.535 MiB
#8 Accepted 135ms 6.383 MiB
#9 Accepted 340ms 6.5 MiB
#10 Accepted 327ms 6.453 MiB

很水的做法:
离线处理最终状态,并查集特判不同列情况

``````#include<iostream>
#include<cmath>
using namespace std;
int n=30000,q,fa[30001],f[30001],ta[30001],val[30001];
struct cz{
char c;
int a,b;
}op[500001];
int find(int);
int main(){
ios::sync_with_stdio(false);
cin>>q;
int i,p;
for(i=1;i<=n;i++){
fa[i]=f[i]=ta[i]=i;
}
for(i=1;i<=q;i++){
cin>>op[i].c;
cin>>op[i].a>>op[i].b;
if(op[i].c=='M'){
int x=find(op[i].a),y=find(op[i].b);
fa[x]=y;
f[x]=ta[y];
ta[y]=ta[x];
ta[x]=0;
}
}
p=0;
for(i=1;i<=n;i++){
fa[i]=i;
if(ta[i]==0) continue;
int v=ta[i];
val[v]=++p;
while(f[v]!=v){
v=f[v];
val[v]=++p;
}
}
for(i=1;i<=q;i++){
int a=find(op[i].a),b=find(op[i].b);
if(op[i].c=='M'){
fa[a]=b;
}else{
if(a!=b){
cout<<-1<<endl;
continue;
}
cout<<abs(val[op[i].a]-val[op[i].b])-1<<endl;
}
}
return 0;
}
int find(int v){
return fa[v]==v?v:fa[v]=find(fa[v]);
}
``````
• @ 2015-08-02 21:25:44

const
maxn=30000;
type
node=record
p,d,l :integer;
end;
var
uf :array[1..maxn]of node;
n,m :longint;
a,b,i :longint;
c :char;
procedure init;
var
i :integer;
begin
n:=30000;
for i:=1 to n do
with uf[i] do begin p:=i; l:=1 end;
end;

function find(x:integer):integer;
var
i,j,p,q :integer;
begin
i:=x;
while uf[i].p<>i do i:=uf[i].p;
p:=i;
i:=x;
while i<>p do
begin
q:=uf[i].p;
uf[i].p:=p;
j:=q;
repeat
inc(uf[i].d,uf[j].d);
j:=uf[j].p
until uf[j].p=j;
i:=q;
end;
find:=p;
end;

procedure union(a,b:integer);
var
t :integer;
begin
a:=find(a); b:=find(b);
uf[a].p:=b;
uf[a].d:=uf[b].l;
inc(uf[b].l,uf[a].l)
end;
begin
init;
for i:=1 to m do
begin
if c='M' then union(a,b);
if c='C' then
if (find(a)=find(b)) then
writeln(abs(uf[a].d-uf[b].d)-1)
else writeln(-1)
end;
end.

• @ 2018-02-05 04:22:27

从并查集本身树结构思考

``````#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define MAXN 30005
using namespace std;

int ufs[MAXN], dis[MAXN] = {0}, ecnt[MAXN];

void init(int n){
for(int i=0; i<=n; i++){
ufs[i] = i;
ecnt[i] = 1;
}
return;
}

int find(int a){
int rt = a, ta = a, tta, tcnt;
int cnt = 0;
while(ufs[rt] != rt){
cnt += dis[rt];
rt = ufs[rt];
}
while(ufs[ta] != ta){
tta = ta;
tcnt = dis[ta];
dis[ta] = cnt;
cnt -= tcnt;
ta = ufs[ta];
ufs[tta] = rt;
}
return rt;
}

void unite(int a, int b){
int rta, rtb;
int tcnta, tcntb;
rta = find(a);
rtb = find(b);
if(rta == rtb){
return;
}
ufs[rta] = rtb;
tcnta = ecnt[rta];
tcntb = ecnt[rtb];
ecnt[rta] = 0;
ecnt[rtb] = tcnta + tcntb;
dis[rta] = tcntb;
return;
}

int sameufs(int a, int b){
if(a == b){
return 0;
}
if(find(a) != find(b)){
return -1;
}else{
return abs(dis[a] - dis[b]) - 1;
}
}

int main(){
int n;
string s;
cin >> n;
int x, y;
init(30000);
for(int i=0; i<n; i++){
cin >> s >> x >> y;
if(s == "M"){
unite(x, y);
}else if(s == "C"){
cout << sameufs(x, y) << endl;
}

}

return 0;
}

``````
• @ 2024-02-03 14:32:46

经典并查集+预先处理
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
typedef long long ll;
//priority_queue<int> a;
//priority_queue<int,vector<int>,greater<int> > a1;
int n,m,k;
//continue;
int a,b;
int f[N],w[N];
char w1[2];
int rk[N];
int getfather(int x)
{
if(f[x]==x)
return x;
int tmp=f[x];
f[x]=getfather(f[x]);
rk[x]=rk[tmp]+rk[x]-1;
return f[x];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=N;i++)
{
f[i]=i;
w[i]=1;
rk[i]=1;
}
for(int i=1;i<=n;i++)
{
scanf("%s %d %d",w1,&a,&b);
int u=getfather(a);
int v=getfather(b);
if(w1[0]=='M')
{
if(u!=v)
{
f[v]=u;
rk[v]+=w[u];
w[u]+=w[v];
}
}
else
{
if(u!=v)
printf("-1\n");
else
printf("%d\n",abs(rk[a]-rk[b])-1);
}
}
return 0;
}
//2434

• @ 2017-01-16 19:32:42

wc这道题疯狂拉AC率。
我写了两份代码，第一份T了最后两个点，然后在第二份中修改，结果每次提交成了第一份。
TLE的原因是用了cin。被卡常了。真是zz。

• @ 2016-11-16 21:58:42
• @ 2016-10-12 13:04:45

#include<iostream>
using namespace std;
int pre[30001];
int find(int x)
{
int r=x;
while(pre[r]!=r)
r=pre[r];

int i=x,j;
while(i!=j)
{
j=pre[r];
pre[i]=r;
i=j;
}
return r;
}
void mix(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
pre[fx]=fy;
}
int main()
{
int i,t,a,b,j;
char g;
for(i=1;i<=30000;i++)
pre[i]=i;
cin>>t;
for(i=1;i<=t;i++)
{
cin>>g>>a>>b;
if(g=='M')
{
mix(a,b);
}
if(g=='C')
{
if(find(a)==find(b))
cout<<"1"<<endl;
else
cout<<"-1"<<endl;
}
}

}

• @ 2016-08-24 08:36:23
``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF = 1000000000;
const int maxn = 30000 + 10;

int p[maxn], d[maxn], cnt[maxn];

int find (int x) {
if (x == p[x]) return x;
int root = find(p[x]);
d[x] += d[p[x]];
return p[x] = root;
}

void comb (int x, int y) {
int a = find(x), b = find(y);
p[b] = a;
d[b] = cnt[a];
cnt[a] += cnt[b];
}

int query (int x, int y) {
int a = find(x), b = find(y);
if (a != b) return -1;
return abs(d[x]-d[y])-1;
}

int main ()
{
freopen("in.txt", "r", stdin);
for (int i = 0; i < maxn; i++) { p[i] = i; cnt[i] = 1;}
int T; scanf("%d\n", &T);
while (T--) {
char code;
int i, j;
scanf("%c %d %d\n", &code, &i, &j);
if (code == 'M') comb(j, i);
else printf("%d\n", query(i, j));
}
return 0;
}
``````
• @ 2016-07-22 11:30:32

#include<cstdio>

#include<cmath>

const int Max=30001;

int t,father[Max],x,y,r[Max],root[Max];

char ch;

int find(int k){

if(k==father[k]) return k;

int temp=find(father[k]);

r[k]=r[father[k]]+r[k];

father[k]=temp;

return temp;

}

int main(){

scanf("%d",&t);

for(int i=1;i<Max;i++){

father[i]=i; r[i]=0,root[i]=1; //r表示到根节点的距离

} //root 表示该树节点个数

while(t--){

getchar();

scanf("%c%d%d",&ch,&x,&y);

int tempx=find(x),tempy=find(y);

if(ch=='M'){

father[tempx]=tempy; //X 接到 y

r[tempx]=root[tempy]; //更新距离

root[tempy]+=root[tempx]; //更新树节点个数

}

else if(tempx!=tempy) printf("-1\n");

else printf("%d\n",(int)fabs(r[x]-r[y])-1);

}

return 0;

}

• @ 2016-07-09 16:50:39
``````#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int f[30001],s[30001],sum[30001];
char ch_buffer;
int signum;
x=0;char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+c-'0';
}
int find(int v){
if(f[v]!=v){
int p=find(f[v]);
s[v]+=s[f[v]];
f[v]=p;
}
return f[v];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
//freopen("in.in","r",stdin);
int f1,f2,num,a,b;
char ch;
for(int i=1;i<=30000;i++){sum[i]=1;f[i]=i;}
for(int i=1;i<=num;i++){
ch=getchar();
f1=find(a),f2=find(b);
//cout<<a<<b;
if(ch=='M'){
f[f1]=f2;
s[f1]=sum[f2];
sum[f2]+=sum[f1];
}
else{
if(f1==f2)cout<<abs(s[a]-s[b])-1<<"\n";
else cout<<"-1\n";
}
}
return 0;
}
``````
• @ 2016-02-25 19:47:31
``````//直接并查集~~
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAXN 31000
using namespace std;

struct node
{
int fa;
int d;//i飞船前面有多少飞船 b
int l;//当i是并查集根时，i后面有多少飞船 c
};
char flag;
node f[MAXN];
int i,t,x,y;

int getfather (int x)
{
int t;
if (x==f[x].fa) return x;
t=f[x].fa;
f[x].fa=getfather(f[x].fa);
f[x].d+=f[t].d;
return f[x].fa;
}

void merg (int x,int y)
{
int tx=getfather(x);
int ty=getfather(y);
if (tx!=ty)
{
f[tx].fa=ty;
f[tx].d=f[ty].l+1;
f[ty].l=f[ty].l+f[tx].l+1;
}
}

int query (int x,int y)
{
if (getfather(x)==getfather(y))
return (abs(f[x].d-f[y].d)-1);
else return -1;
}

int main()
{
for (i=1;i<=MAXN;i++)
{
f[i].fa=i;
f[i].d=0;
f[i].l=0;
}
scanf("%d\n",&t);
for (i=1;i<=t;i++)
{
scanf("%c %d %d\n",&flag,&x,&y);
if (flag=='M')
merg(x,y);
else
printf("%d\n",query(x,y));
}
return 0;
}
``````
• @ 2015-11-15 22:56:23

P1443银河英雄传说
Accepted

记录信息

评测状态 Accepted
题目 P1443 银河英雄传说
递交时间 2015-11-15 22:55:41
代码语言 C++
评测机 VijosEx
消耗时间 5238 ms
消耗内存 628 KiB
评测时间 2015-11-15 22:55:49

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 628 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 628 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 628 KiB, score = 10

测试数据 #3: Accepted, time = 62 ms, mem = 624 KiB, score = 10

测试数据 #4: Accepted, time = 202 ms, mem = 628 KiB, score = 10

测试数据 #5: Accepted, time = 483 ms, mem = 624 KiB, score = 10

测试数据 #6: Accepted, time = 499 ms, mem = 628 KiB, score = 10

测试数据 #7: Accepted, time = 639 ms, mem = 624 KiB, score = 10

测试数据 #8: Accepted, time = 1856 ms, mem = 628 KiB, score = 10

测试数据 #9: Accepted, time = 1482 ms, mem = 624 KiB, score = 10

Accepted, time = 5238 ms, mem = 628 KiB, score = 100

why so slow

代码

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int pre[30000 + 2] , size[30000 + 2] , tail[30000 + 2];
int n , a , b , x , y;
char s[10];

int find( int x )
{
if( pre[x] == x ) return x;
int pos = pre[x];
pre[x] = find( pre[x] );
size[x] += size[pos];
return pre[x];
}

inline void merge( int a , int b )
{
pre[ find( a ) ] = find( b );
}

inline int Abs( int x )
{
return x > 0 ? x : -x;
}

int main()
{
scanf( "%d" , &n );
for( register int i = 1 ; i <= 30000 ; i++ )
pre[i] = i , tail[i] = 1;
while( n-- )
{
scanf( "%s %d %d" , s , &a , &b );
if( s[0] == 'C' )
{
if( find( a ) != find( b ) ) puts( "-1" );
else printf( "%d\n" , Abs( size[a] - size[b] ) - 1 );
}
else
{
x = find( a ) , y = find( b );
merge( a , b );
size[ x ] += tail[ y ];
tail[ y ] += tail[ x ];
}
}
return 0;
}

• @ 2015-03-14 14:22:22

感觉只能用链式并查集来维护一些神奇的东西?.....
使用启发式合并达到O(nlogn)的复杂度......

• @ 2014-10-03 14:55:27

#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
char t;
int m,q,a,b,f[30001],o[30001]={0},c[30001];
void r(int&d)
{
char t=getchar();
while(t<'0'||t>'9')
t=getchar();
for(d=0;t>='0'&&t<='9';t=getchar())
d=(d<<3)+(d<<1)+t-'0';
}
int find(int n)
{
int d;
if(n==f[n])
return n;
else
{
d=find(f[n]);
o[n]+=o[f[n]];
f[n]=d;
return f[n];
}
}
bool e(int x,int y)
{
int p,q;
p=find(x);
q=find(y);
if(p==q)
return 1;
else
{
f[q]=p;
o[q]+=c[p];
c[p]+=c[q];
return 0;
}
}
main()
{
char k[100];
int d,i,j;
cin>>q;
for(i=1;i<30001;i++)
{
f[i]=i;
c[i]=1;
}
for(i=0;i!=q;i++)
{
t=getchar();
while(t!='M'&&t!='C')
t=getchar();
r(a);
r(b);
if(t=='M')
e(a,b);
else
if(find(a)==find(b))
{
d=abs(o[b]-o[a])-1;
j=1;
if(d<0)
{
cout<<'-';
d=-d;
}
if(!d)
cout<<0;
for(;d;d/=10,j++)
k[j]=d%10+'0';
for(j--;j;j--)
cout<<k[j];
cout<<endl;
}
else
cout<<-1<<endl;
}
}

• @ 2014-08-24 13:50:49

#include<cstdio>

int n=30000,m,q;
int ai,bi;
int fath[30001];
int count[30001];
int before[30001];
char t;
inline void _out(int x,int j=1)

{

char t[100];

if(x<0)

{

putchar('-');

x=-x;

}

if(x==0) printf("0");

for(;x;x/=10,j++) t[j]=x%10+'0';

for(j--;j;j--) putchar(t[j]);

putchar('\n');

}

{
char t=getchar();
while(t<'0'||t>'9') t=getchar();
for(data=0;t>='0'&&t<='9';t=getchar()) data=(((data)<<3)+((data)<<1))+t-'0';
}

int getfather(int num)
{
if(num==fath[num]) return num;
else
{
before[num]=before[num]+before[fath[num]];
return fath[num];
}
}
bool merge(int x,int y)
{
int fx,fy ;
fx=getfather(x);
fy=getfather(y);
if (fx==fy) return true;
else
{
fath[fy]=fx;
before[fy]=before[fy]+count[fx];
count[fx]=count[fx]+count[fy];
return false;
}
}

inline void _init()
{
scanf("%d",&q);
for(int i=1;i<=n;++i)
{fath[i]=i;count[i]=1;before[i]=0;}
}
inline int abs(int a)
{return a<0?(-a):a;}
int main()
{
_init();
for(int i=0;i!=q;++i)
{
t=getchar();
while(t!='M'&&t!='C') t=getchar();
else
if(getfather(ai)==getfather(bi))_out((abs(before[bi]-before[ai]))-1);
else {putchar('-');putchar('1');putchar('\n');}
}
}
return 0;
}

• @ 2013-10-14 15:57:54

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long f[30100],s[30100],sum[30100];
int getfather(int v){
if (f[v]!=v){
int p=getfather(f[v]);
s[v]+=s[f[v]];
f[v]=p;
}return f[v];
}
int main(){
int f1,f2,num,a,b; char ch;
scanf("%d\n",&num);
for(int i=1;i<=30000;i++) {s[i]=0; sum[i]=1; f[i]=i;}
for(int i=1;i<=num;i++){
scanf("%c %d %d\n",&ch,&a,&b);
f1=getfather(a),f2=getfather(b);
if(ch=='M'){
f[f1]=f2;
s[f1]=sum[f2];
sum[f2]+=sum[f1];
}else if(ch=='C'){
if(f1==f2) printf("%d\n",abs(s[a]-s[b])-1);

else printf("-1\n");

}
}
return 0;
}

• @ 2013-08-13 12:55:31

编译成功

foo.cpp: In function 'int main()':
foo.cpp:57:26: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1]' [-Wformat]
测试数据 #0: Accepted, time = 7 ms, mem = 1004 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1004 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1004 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1000 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 1004 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 1004 KiB, score = 10
测试数据 #6: Accepted, time = 140 ms, mem = 1000 KiB, score = 10
测试数据 #7: Accepted, time = 203 ms, mem = 1004 KiB, score = 10
测试数据 #8: Accepted, time = 343 ms, mem = 1004 KiB, score = 10
测试数据 #9: Accepted, time = 468 ms, mem = 1000 KiB, score = 10
Accepted, time = 1331 ms, mem = 1004 KiB, score = 100
#include <cstdio>
#include <cstring>

using namespace std;

#define MAXN 30001

int father[MAXN];
int suff[MAXN];

int t;
char c[1];

int ABS(int x){
if (x<0){
return -x;
}
return x;
}

int INSERT(int x,int y){
father[x]=y;
suff[x]++;
return 0;
}

int find(int x){
int i=x;
int k=0;
while (father[i]){
k+=suff[i];
k--;
i=father[i];
}
k++;
int j=x;
while (father[j]){
int h=father[j],z=suff[j];
suff[j]=k;
k-=(z-1);
father[j]=i;
j=h;
}
return i;
}

int main(){
memset(father,0,sizeof(father));
for (int i=0;i++<MAXN;){
suff[i]=1;
}
scanf("%d",&t);
while (t--){
int x,y;
scanf("%s%d%d",&c,&x,&y);
if (c[0]=='M'){
int k=tail[find(x)];
INSERT(find(x),tail[find(y)]);
tail[find(y)]=k;
} else {
if (find(x)!=find(y)){
printf("-1\n");
} else printf("%d\n",ABS(suff[x]-suff[y])-1);
}
}
return 0;
}

• @ 2010-04-16 12:36:13

VJ脑残的输出

无语了

• @ 2010-03-18 13:48:00

我无语...自己机上测这条题（使用VJ数据）近乎秒，这里超时+格式错误+答案错误....T-T

• @ 2009-11-19 20:26:26

#include

#include

using namespace std;

struct a

{

int d;

int p;

int z;

}f[30001];

int find(int i)

{

if(f[i].p!=i)

{

int r=find(f[i].p);

f[i].d+=f[f[i].p].d;

f[i].p=r;

}

return f[i].p;

}

int main(void)

{

//FILE *fp1=fopen("galaxy.in","r"),*fp2=fopen("galaxy.out","w");

int t,i,a,b,ar,br;

char p;

for(i=1;i

ID
1443

7

3503

715

20%

6