本文主要是介绍POJ-1182-食物链（并查集经典题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//传送门:http://poj.org/problem?id=1182
#include <queue>
#include <functional>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <assert.h>
using namespace std;
#define N 100005
//思路： a吃b,b吃c,c吃a 显然是节点3的环；
// 用 0 表示相等的状态， 1 表示吃别人的状态， 2表示被吃的状态。
int pre[N]; // pre[i] 表示 i 的祖先
int flag[N]; //flag[i] 表示i 与其祖先的关系
int getf(int x) //递归求祖先节点的同时，更新其与祖先的关系
{int tmp = pre[x]; //保存原来的祖先节点pre[x]= x==pre[x]?x:getf(pre[x]); flag[x] = (flag[x]+flag[tmp]) % 3; return pre[x];
}
inline void union_(int x,int y,int value) //合并
{ pre[x] = y;flag[x] = value;
}
int main()
{int n,k;scanf("%d%d",&n,&k);int ans = 0;for(int i=1;i<=n;i++) pre[i]=i,flag[i]=0;while(k--){int d,x,y;scanf("%d%d%d",&d,&x,&y);if(x>n || y>n || (d==2&&x==y)) ans++;else{d--; //方便操作，与思路中的状态定义相对应int fa = getf(x);int fb = getf(y);if(fa==fb){ //如果同祖先//printf("%d %d %d\n",fa,flag[x],flag[y]);//cout<<(d+3-flag[x]+flag[y])%3<<endl;if( (d+3-flag[x]+flag[y])%3) ans++; //则判断是否成一个完整的环 若完整 值为0}else{union_(fa,fb,(3-flag[x]+d+flag[y])%3); // 若不同祖先则合并 置flag[fa] 为 fa 到 fb 的关系 }}} printf("%d\n",ans);
}
这篇关于POJ-1182-食物链（并查集经典题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
