写了几个查并集得题，成功把自己写晕了
之后写下面得题（写不下去了）
**poj-2912
poj
文章目录
1.POJ - 1611（模板题）
题意：一共有n个人，m个队伍，告诉你一个人得了病毒，然后与他在一个小队的人也会有问题，而且一个人可能不仅仅仅在一个小队出现过。问一共有多少人可能会有问题。
代码：
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 110
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
int a[30010];
int n,m;
int ifind(int x){
if(x==a[x]) return x;
return a[x]=ifind(a[x]);
}
int main()
{
while(cin>>n>>m&&n){
for(int i=0;i<=n;i++) a[i]=i;
int num;
for(int f=0;f<m;f++){
cin>>num;
int x,y;
for(int i=0;i<num;i++){
cin>>y;
if(i==0){
x=y;
continue;
}
int dx=ifind(x);
int dy=ifind(y);
if(dx!=dy) a[dx]=dy;
}
}
int ans=0;
int k=ifind(0);
for(int i=0;i<n;i++){
if(k==ifind(i)) ans++;
}
cout<<ans<<endl;
}
return 0;
}
2.HDU - 1213（模板题）
给定n个人，m个关系，并且符合朋友的朋友也是朋友，问问最多有多少组关系。
代码：
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 110
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
int f[30010];
int n,m;
int ifind(int x){
if(x==f[x]) return x;
return f[x]=ifind(f[x]);
}
int main()
{
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++) f[i]=i;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
int dx=ifind(x);
int dy=ifind(y);
if(dx!=dy) f[dx]=dy;
}
int ans=0;
for(int i=1;i<=n;i++){
if(f[i]==i) ans++;
}
cout<<ans<<endl;
}
return 0;
}
3.poj2236（稍稍复杂的查并集）
一开始犯了一个小错误（每次修复只进行了与其相邻的增加操作）当然这显然是不行的，反正时间10000ms，直接暴力吧，每次都把他扫一遍就可以了
时间：4157ms
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 110
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
int f[30010];
int n,d;
int ifind(int x){
if(x==f[x]) return x;
return f[x]=ifind(f[x]);
}
int visited[30010];
struct wazxy{
double x,y;
}a[30010];
void solve(int x,int y){
double dis;
dis=sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
if(dis<=d){
// cout<<"ok"<<endl;
int dx=ifind(y);
int dy=ifind(x);
if(dx!=dy) f[dx]=dy;
}
}
int main()
{
cin>>n>>d;
for(int i=0;i<=n;i++) f[i]=i;
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
getchar();
char c;
while(cin>>c){
int x,y;
if(c=='O'){
cin>>x;
visited[x]=true;
for(int i=1;i<=n;i++){
if(x==i) continue;
if(visited[i])
solve(x,i);
}
}
else{
cin>>x>>y;
int dx=ifind(x);
int dy=ifind(y);
if(dx==dy) cout<<"SUCCESS"<<endl;
else cout<<"FAIL"<<endl;
}
}
// for(int i=1;i<=n;i++) cout<<f[i]<<" ";
return 0;
}
4.HDU - 1272（查并集判断图是否连通）
这个题的话题目考察的还是看看是否有环且这个图是不是一个连通图，这个图比较特殊，是一个无向图，但是每条边只可以走一次
因为这个题并不是某个范围内的每个点都会出现，所以我们需要一个visited来记录该点是否出现，从而辅助判断图是否联通
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 100010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
int f[100010];
bool visited[100010];
int ifind(int x){
if(x==f[x]) return x;
return f[x]=ifind(f[x]);
}
bool imerge(int x,int y){
int dx=ifind(x);
int dy=ifind(y);
if(dx==dy) return true;
else f[dx]=dy;
return false;
}
int main()
{
int n,m;
while(cin>>n>>m&&n!=-1){
for(int i=0;i<maxn;i++) f[i]=i;
memset(visited,false,sizeof(visited));
bool flag=true;
while(n||m){
visited[n]=true;
visited[m]=true;
if(imerge(n,m)) flag=false;
scanf("%d%d",&n,&m);
}
int ans=0;
for(int i=1;i<maxn;i++){
if(visited[i]&&f[i]==i){
ans++;
}
}
if(ans>1) flag=false;
if(flag==false) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}
5.poj-1308(跟上面的题目很像)（只是多加了入读这个条件而已）
这个题目跟hdu1325的描述完全一致，但是你会发现ac poj但是ac不了hdu
一开始还以为poj的数据太水，实则不然。去网上查了查，网上的意思是说这两道题目两个oj对其的理解不同，所以才导致这样的情况发生。
条件为：
1.只有一个入度为0的点，作为根节点。
2.除根节点外，其他点的入度只能为1。
3.所有点都能连通。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 100030
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
int f[maxn];
int in[maxn];
bool visited[maxn];
int ifind(int x){
if(x==f[x]) return x;
return f[x]=ifind(f[x]);
}
bool imerge(int x,int y){
int dx=ifind(x);
int dy=ifind(y);
if(dx==dy) return true;
else f[dx]=dy;
return false;
}
int main()
{
int n,m;
int z=1;
while(cin>>n>>m&&n!=-1){
for(int i=0;i<maxn;i++) f[i]=i;
memset(visited,false,sizeof(visited));
memset(in,0,sizeof(in));
bool flag=true;
if(n==0&&m==0){
printf("Case %d is a tree.\n",z++);
continue;
}
while(n||m){
visited[n]=true;
visited[m]=true;
in[m]++;
if(imerge(n,m)) flag=false;
scanf("%d%d",&n,&m);
}
int ans=0,cnt=0;
for(int i=1;i<maxn;i++){
if(visited[i]&&in[i]==0){
ans++;
}
if(in[i]>=2) flag=false;
if(visited[i]&&f[i]==i) cnt++;
}
if(ans!=1||cnt>1) flag=false;
if(flag==false) printf("Case %d is not a tree.\n",z++);
else printf("Case %d is a tree.\n",z++);
}
return 0;
}
6.poj-1456(此题纯属乱入)贪心解决125ms
这题一看，跟以前做过的一个贪心题不是一模一样吗，为什么要用查并集优化，算了不优化了直接贪心写吧，125ms，然后交了一下查并集的方法做的76ms，也没差太多，算了不学了，还是直接贪心香啊。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 10010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
int visited[maxn];
struct wazxy{
int deadline;
int val;
}a[maxn];
struct rule{
bool operator ()(const wazxy & a,const wazxy & b){
return a.val>b.val;
}
};
int main()
{
int n;
while(cin>>n){
int ans=0;
for(int i=1;i<=n;i++) scanf("%d %d",&a[i].val,&a[i].deadline);
sort(a+1,a+1+n,rule());
//for(int i=1;i<=n;i++) cout<<a[i].val<<endl;
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++){
for(int j=a[i].deadline;j>=1;j--){
if(visited[j]==false){
ans+=a[i].val;
visited[j]=true;
break;
}
}
}
cout<<ans<<endl;
}
return 0;
}
7.HDU - 3038（带权的查并集）
从本题往后就是带权的查并集的应用了，当然要注意一点，就是使用路径压缩时，他权值的更新操作，主要时递归一层一层来计算的
给出一个区间的长度 N，及 M 个子区间和， 形如：x y z, 表示子区间 [x, y] 的和为 z，如果一个“子区间和”与前面的“子区间和”冲突，即为错误（而且这个“子区间和”将在接下来的判断中被忽略）。
求总错误个数。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 200010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
int f[maxn];
int cnt[maxn];
int n,m;
int ifind(int x){
if(x!=f[x]){
int fa=f[x];
f[x]=ifind(f[x]);
cnt[x]+=cnt[fa];
}
return f[x];
}
void init(){
for(int i=0;i<=n;i++){
f[i]=i;
cnt[i]=0;
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
int ans=0;
init();
int u,v,w;
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
int dx=ifind(u-1);
int dy=ifind(v);
if(dx==dy){
if(cnt[u-1]+w!=cnt[v]) ans++;
}
else{
f[dy]=dx;
cnt[dy]=cnt[u-1]-cnt[v]+w;
}
}
cout<<ans<<endl;
}
return 0;
}
8.poj-1733（查并集+离散化）
天呐poj网站维护，明天才能提交，先写上吧，虽然可能会wa。
第一次接触离散化，因为数据太大了，此时就可以用map这个容器。离散化可以简单理解为，把很大的一个数转化成比较小的一个数，那就通过map这个容器可以做到了，为了保证转化唯一，就可以用cnt++从而保证了转化后的数据不会冲突。
很庆新今早上再次提交ac了
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 10010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
map<int ,int> mp;
int val[maxn],f[maxn];
int cnt;
void init(){
for(int i=0;i<maxn;i++) f[i]=i;
memset(val,0,sizeof(val));
cnt=0;
}
int ins(int x){
if(mp.find(x)==mp.end()) mp[x]=cnt++;
return mp[x];
}
int ifind(int x){
if(f[x]==x){
return x;
}
int temp=ifind(f[x]);
val[x]^=val[f[x]];
return f[x]=temp;
}
bool solve(int x,int y,int z){
int dx=ifind(x);
int dy=ifind(y);
if(dx==dy){
if(val[x]^val[y]==z) return true;
else return false;
}
else{
f[dx]=dy;
val[dx]=val[x]^val[y]^z;
return true;
}
}
int main()
{
init();
int n,m;
cin>>n>>m;
char a[10];
for(int i=0;i<m;i++){
int x,y,z;
scanf("%d%d%s",&x,&y,a);
x=ins(x-1);
y=ins(y);
if(a[0]=='e') z=0;
else z=1;
if(!solve(x,y,z)){
cout<<i<<endl;
return 0;
}
}
cout<<m<<endl;
return 0;
}
9.poj2492（种类查并集）
跟上面的第八题极其相似，让我知道了位运算的强大之处。
我们可以用val[x]数组来记录x与父亲节点的关系，如果后面的结果与前面的产生矛盾，那么就说后面的出错了
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 10010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
bool flag=true;
int val[maxn],f[maxn];
int cnt=1;
void init(){
for(int i=0;i<maxn;i++) f[i]=i;
memset(val,0,sizeof(val));
flag=true;
}
int ifind(int x){
if(f[x]==x){
return x;
}
int temp=ifind(f[x]);
val[x]^=val[f[x]];
return f[x]=temp;
}
bool solve(int x,int y){
int dx=ifind(x);
int dy=ifind(y);
if(dx==dy){
if(val[x]^val[y]==1) return true;
else return false;
}
else{
f[dx]=dy;
val[dx]=val[x]^val[y]^1;
return true;
}
}
int main()
{
int n,m;
int t;
cin>>t;
while(t--){
init();
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,z;
scanf("%d%d",&x,&y);
if(flag==false) continue;
if(!solve(x,y)){
flag=false;
}
}
if(flag==false) printf("Scenario #%d:\nSuspicious bugs found!\n\n", cnt++);
else printf("Scenario #%d:\nNo suspicious bugs found!\n\n", cnt++);
}
return 0;
}
10.poj-1182（经典带权查并集例题）
看网上说这个题是入门带权查并集十分经典得一个题目，当然如果让我推导像代码中得公式，那可能性一般为0，但是网上有很多好资源啊，就比如说下面的链接那篇博客，我觉得讲的可以说是非常棒了。
https://blog.csdn.net/weixin_44758733/article/details/104220585
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 100010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
int n,m;
int val[maxn];
int f[maxn];
int ans=0;
void init(){
for(int i=0;i<maxn;i++){
val[i]=0;
f[i]=i;
}
}
int ifind(int x){
if(x!=f[x]){
int temp=f[x];
f[x]=ifind(f[x]);
val[x]=(val[x]+val[temp])%3;
}
return f[x];
}
void solve(int x,int y,int z){
int dx=ifind(x);
int dy=ifind(y);
if(dx==dy){
if(z==1&&val[x]!=val[y]) ans++;
if(z==2&&(val[x]+1)%3!=val[y]) ans++;
}
else{
f[dy]=dx;
val[dy]=(3-val[y]+z-1+val[x])%3;
}
}
int main()
{
cin>>n>>m;
init();
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&z,&x,&y);
if(x>n||y>n) ans++;
else if(z==2&&x==y) ans++;
else solve(x,y,z);
}
printf("%d\n",ans);
return 0;
}
种类查并集实在是给我查迷糊了，留两个题以后写
（其实我写不下去了）
poj-2912
poj-1984
得出结论：kuangbin也救不了我。
京公网安备 11010502036488号