本文主要是介绍POJ 1703 POJ 2492 并查集 和 食物链差不多，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
用 a 表示 a 在组织 1 ，a+MAX 表示 a 在组织2
遇到 D，就把 a 在组织1 和 b在组织2 放入一个集合，把 a 在组织2 与 b 在组织 1 放入一个集合。
若查相同，则 same(a,b) 为true
若查不同，则 same(a,a+MAX) 为 true
否则就是不确定
这个题在查的时候是使用 || 来查 和使用 && 来查是一样滴，因为只给出 a b 不同是无法只出现一种答案的。
写并查集的时候。。。join 能不能别写SB 了。。。要两个父亲之间合并。。。
POJ 1703
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include <set>
#include <stack>using namespace std;#define READ freopen("acm.in","r",stdin)
#define WRITE freopen("acm.out","w",stdout)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define MII map<int,int>::iterator
#define fst first
#define sec second
#define MS(x,d) memset(x,d,sizeof(x))
#define INF 0x3f3f3f3f
#define ALL(x) x.begin(),x.end()
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ROOT 0,n-1,1
#define PB push_back
#define FOR(a,b,c) for(int a=b;a<c;a++)
#define MOD 1000000007
#define keyTree (ch[ ch[root][1] ][0])
#define MAX 111111int pre[MAX<<1];
void init()
{for(int i=0;i<(MAX<<1);i++)pre[i]=i;
}int find(int x)
{return x==pre[x]?x:pre[x]=find(pre[x]);
}bool same(int x,int y)
{return find(x)==find(y);
}
void join(int x,int y)
{int fx=find(x),fy=find(y);// Noticepre[fx]=pre[fy];
}
int main()
{READ; int cas;scanf("%d",&cas);while(cas--){init();int n,m;scanf("%d%d",&n,&m);for(int i=0;i<m;i++){char op[3];int a,b;scanf("%s%d%d",op,&a,&b);//cout<<same(a,b)<<endl;if(op[0]=='A'){if(same(a,b)&&same(a+MAX,b+MAX))puts("In the same gang.");else if(same(a+MAX,b)&&same(a,b+MAX))puts("In different gangs.");elseputs("Not sure yet.");}if(op[0]=='D'){join(a,b+MAX);join(b,a+MAX);}}}return 0;
}POJ 2492
和上一道题目基本完全一样。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include <set>
#include <stack>using namespace std;#define READ freopen("acm.in","r",stdin)
#define WRITE freopen("acm.out","w",stdout)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define MII map<int,int>::iterator
#define fst first
#define sec second
#define MS(x,d) memset(x,d,sizeof(x))
#define INF 0x3f3f3f3f
#define ALL(x) x.begin(),x.end()
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ROOT 0,n-1,1
#define PB push_back
#define FOR(a,b,c) for(int a=b;a<c;a++)
#define MOD 1000000007
#define keyTree (ch[ ch[root][1] ][0])
#define MAX 111111int pre[MAX<<1];
void init()
{for(int i=0;i<(MAX<<1);i++)pre[i]=i;
}int find(int x)
{return x==pre[x]?x:pre[x]=find(pre[x]);
}bool same(int x,int y)
{return find(x)==find(y);
}
void join(int x,int y)
{int fx=find(x),fy=find(y);pre[fx]=pre[fy];
}
int main()
{READ; int cas;scanf("%d",&cas);for(int T=1;T<=cas;T++){printf("Scenario #%d:\n",T);init();int n,m;scanf("%d%d",&n,&m);bool flag=true;for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);if(true&&same(a,b))flag=false;join(a,b+MAX);join(a+MAX,b);}if(flag)puts("No suspicious bugs found!\n");elseputs("Suspicious bugs found!\n");}return 0;
}这篇关于POJ 1703 POJ 2492 并查集 和 食物链差不多的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
