M_sea

洛谷2024 食物链
Luogu算法基本思想建立三个并查集,分别代表A、B、C。基本操作对于操作1,在每一个并查集中将这两个动物合并。对...
扫描右侧二维码阅读全文
18
2018/07

洛谷2024 食物链

Luogu

算法

基本思想
建立三个并查集,分别代表A、B、C。

基本操作
对于操作1,在每一个并查集中将这两个动物合并。

对于操作2,即x吃y,那么把A中的x和B中的y合并、把B中的x和C中的y合并,把C中的x和A中的y合并。

如何判断两种动物是同类
如果A吃B或者B吃A,那它们就不是同类。

如何判断A吃B
如果A和B是同类或者B吃A,那么A就不吃B。

最后
细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int root[50000*3+10];
inline int find(int u) {
    if (root[u]!=u) root[u]=find(root[u]);
    return root[u];
}
inline void merge(int u,int v) {
    u=find(u),v=find(v);
    if (u!=v) root[u]=v;
}

int main() {
    int n,k,ans=0;
    n=read(),k=read();
    for (re int i=1;i<=n*3;i++) root[i]=i;
    for (re int i=1;i<=k;i++) {
        int op,X,Y; op=read(),X=read(),Y=read();
        if (X>n||Y>n) { ans++; continue; }
        if (op==1) {
            if (find(X)==find(Y+n)||find(X+n)==find(Y)) ans++;
            else { merge(X,Y); merge(X+n,Y+n); merge(X+n+n,Y+n+n); }
        }
        else if (op==2) {
            if (find(X)==find(Y)||find(X+n)==find(Y)) ans++;
            else { merge(X,Y+n); merge(X+n,Y+n+n); merge(X+n+n,Y); }
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 33 PM

发表评论