NOIP模拟题 by天津南开中学莫凡[tarjan][树剖][并查集]

本文主要是介绍NOIP模拟题 by天津南开中学莫凡[tarjan][树剖][并查集]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考试总结：
解题报告：
一．图的连通性：
题意：给定一图，动态删边，动态求是否连通，且查询中输入的变量需xor当前边数才为最终输入数据；
分析：只删边则可以逆向建边用并查集查询是否连通，并查集基本上也是现阶段唯一一种可以在线快速求联通的算法了；
具体实现的话，先把边用康托展开转化为n+1进制的数，再用map去映射一个编号，然后两个mapy一个通过编号存储边出现次数，一个通过编号存储这条边的数便于反向查找；然后删边用map映射编号然后删map就可以了，最后反向连图加求联通；
程序：

#include<iostream>
#include<cstdio>
#include<map>
#define ll long long
using namespace std;
map<long long ,int>roa;
const int maxn=150000+5;
int mapy[maxn],n,m,t,sta,fin,fa[maxn],inde,tmp1[maxn];
int tmp2[maxn],tmp3[maxn],ans[maxn];
long long mapy2[maxn];
ll calc(ll  x,ll y,ll n)
{return x*(n+1)+y;
}
int lookfor(int x)
{if(fa[x]==x)return x;return fa[x]=lookfor(fa[x]);
}
void unionion(int x,int y)
{x=lookfor(x);y=lookfor(y);fa[x]=y;
}
int main()
{freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);scanf("%d %d %d",&n,&m,&t);for(int i=1;i<=m;i++){scanf("%d %d",&sta,&fin);if(sta>fin)swap(sta,fin);if(!roa[calc(sta,fin,n)]){roa[calc(sta,fin,n)]=++inde;mapy2[inde]=calc(sta,fin,n);}mapy[roa[calc(sta,fin,n)]]++;}for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=t;i++){scanf("%d %d %d",&tmp1[i],&tmp2[i],&tmp3[i]);tmp2[i]^=m;tmp3[i]^=m;if(tmp2[i]>tmp3[i])swap(tmp2[i],tmp3[i]);if(tmp1[i]==1){m--;mapy[roa[calc(tmp2[i],tmp3[i],n)]]--;}}for(int i=1;i<=inde;i++)if(mapy[i]){unionion(mapy2[i]/(ll)(n+1),mapy2[i]%(ll)(n+1));}for(int i=t;i>=1;i--){if(tmp1[i]==1){unionion(tmp2[i],tmp3[i]);}else {if(lookfor(tmp2[i])==lookfor(tmp3[i]))ans[i]=