题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66964#problem/E
题目思路:主要有两种思路:1.带权并查集2.挑战程序上的算法(个人理解也算是带权并查集的一种,但是更易懂,思路更清晰)
(介绍挑战上的算法) 将整个数组开到3倍,分3个组,每个组之间的关系确定x,y的关系(判定假话),x,y的关系确定合并哪些组的元素
挑战程序P88
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) #define Min(x,y) (x<y?x:y) #define Max(x,y) (x>y?x:y) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 100000007 #define inf 0x3f3f3f3f #define N 150010 #define maxn 10001000 typedef long long LL; typedef pair<int,int> PII; int fp[N]; int n,m; int findp(int x){return fp[x]==x?x:fp[x]=findp(fp[x]);} inline int same(int x,int y){return findp(x)==findp(y);} inline void Union(int x,int y){int u=findp(x);int v=findp(y);fp[u]=v;} int main() { int i,j,x,y,v,ans; // freopen("lxx.txt","r",stdin); scanf("%d%d",&n,&m);{ for(i=1; i<=n*3; ++i) fp[i]=i; ans=0; while(m--){ scanf("%d%d%d",&v,&x,&y); if(x<1||x>n||y<1||y>n) ++ans; else if(v==2&&x==y) ++ans; else if(v==1){ if(same(x,y+n)||same(x,y+2*n)) ++ans; else{ Union(x,y); Union(x+n,y+n); Union(x+n*2,y+n*2); } } else{ if(same(x,y)||same(x,y+2*n)) ++ans; else{ Union(x,y+n); Union(x+n,y+2*n); Union(x+2*n,y); } } } printf("%d ",ans); } return 0; }
这道题必须单组输入,加EOF就WA,太坑了
参考题解:传送门