AcWing 240. 食物链
原题链接
中等
作者:
牛奶小柒Luke
,
2021-01-26 21:33:58
,
所有人可见
,
阅读 360
并查集
//AcWing 240 食物链
#include <iostream>
using namespace std;
const int N = 200000;
int f[N];
int n,m,k,x,y,ans;
int get(int x){
if(x == f[x]) return x;
return f[x] = get(f[x]);
}
void merge(int x,int y){
f[get(x)] = get(y);
}
int main(){
cin >> n >> m;
for(int i = 1;i <= 3 * n;++i){
f[i] = i;
}
for(int i = 1;i <= m;++i){
cin >> k >> x >> y;
if(x > n || y > n) ans++;
else if(k == 1){
if(get(x) == get(y + n) || get(x) == get(y + n + n)){
ans++;
}else{
merge(x,y);
merge(x + n,y + n);
merge(x + n + n,y + n + n);
}
}else{
if(x == y || get(x) == get(y) || get(x) == get(y + n)){
ans++;
}else{
merge(x,y + n + n);
merge(x + n,y);
merge(x + n + n,y + n);
}
}
}
cout << ans << endl;
return 0;
}