并查集专题

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
int f[99999],a[3009][3099],b[3999];
int ans[19999];
int find(int x)
{
    if(x==f[x])return x;
    int fx=find(f[x]);
    return f[x]=fx; 
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=1;
        a[y][x]=1;
    }
    for(int i=1;i<=n;i++)
    scanf("%d",&b[i]);
    for(int i=n;i>=1;i--)
    {
    
        int fx=find(b[i]);
        for(int j=i;j<=n;j++)
        if(a[b[i]][b[j]])
        {
            
            int fy=find(b[j]);
            f[fy]=fx;
        } 
        int w=0,fz=0;
        for(int j=i;j<=n;j++)
        {
            fz=find(b[j]);
            if(w!=fz&&w!=0) ans[i]++;
            w=fz;
        }
    }
    for(int i=1;i<=n;i++)
    if(ans[i])printf("NOn");
    else printf("YESn"); 
}

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
int f[99999],disx[99999],disy[99999],f1[99999],f2[99999],l[94999];char d[99999];
int w[99999],r[99999],s[99999];
int abs(int x)
{
	return x>0?x:-x;
}
int find(int x)
{
	if(x==f[x])return x;
	int fx=find(f[x]);
	disx[x]+=disx[f[x]];
	disy[x]+=disy[f[x]];
	return f[x]=fx; 
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=1;i<=m;i++)
		{
		
			scanf("%d%d%d",&f1[i],&f2[i],&l[i]);
			cin>>d[i];
		}
		int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		
		scanf("%d%d%d",&w[i],&r[i],&s[i]);
	}
	int j=1;
	for(int i=1;i<=m;i++)
	{
		int fx1=find(f1[i]);
		int fx2=find(f2[i]);
		if(fx1==fx2) continue;
		if(d[i]=='E')
			disx[f1[i]]=disx[f1[i]]-disx[f2[i]]+l[i],disy[f1[i]]=disy[f1[i]]-disy[f2[i]];
		if(d[i]=='W')
		    disx[f1[i]]=disx[f1[i]]-disx[f2[i]]-l[i],disy[f1[i]]=disy[f1[i]]-disy[f2[i]];
		if(d[i]=='N')
		    disy[f1[i]]=disy[f1[i]]-disy[f2[i]]+l[i],disx[f1[i]]=disx[f1[i]]-disx[f2[i]];
		if(d[i]=='S')
		    disy[f1[i]]=disy[f1[i]]-disy[f2[i]]-l[i],disx[f1[i]]=disx[f1[i]]-disx[f2[i]];
		
		f[fx1]=fx2;
		if(s[j]==i){
		 fx1=find(w[j]);
		 fx2=find(r[j]);
		if(fx1!=fx2)
		{
			j++;
			printf("-1n");
			continue;
		}
		printf("%dn",abs(disx[w[j]]-disx[r[j]])+abs(disy[w[j]]-disy[r[j]]));
		j++;
		}
	}
}