POJ1182食物链（并查集经典好题）

程序员志飞技术 2022年11月19日

0 收藏 888 点赞 4,190 浏览 1450 个字

题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66964

题目思路:主要有两种思路：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=; i<=n*; ++i) fp[i]=i;
        ans=;
        while(m--){
            scanf("%d%d%d",&v,&x,&y);
            if(x<||x>n||y<||y>n) ++ans;
            else if(v==&&x==y) ++ans;
            else if(v==){
                if(same(x,y+n)||same(x,y+*n)) ++ans;
                else{
                    Union(x,y);
                    Union(x+n,y+n);
                    Union(x+n*,y+n*);
                }
            }
            else{
                if(same(x,y)||same(x,y+*n)) ++ans;
                else{
                    Union(x,y+n);
                    Union(x+n,y+*n);
                    Union(x+*n,y);
                }
            }
        }
        printf("%d\n",ans);
    }
    return ;
}