[POJ 1182][Disjoint Set] 食物鏈

原題連結
yee~~~這是並查集非常非常經典的一道題。
顯然我1年多前看過，當時自然是沒想出來的XD，現在看就比較清晰了。
看到「同類」最直覺的想法就是用Disjoint set去維護同類關係，但是題目還另外有種關係叫做A吃B，這要怎麼做呢？

以下直接提供想法，類似的想法也蠻常出現在一些趣題上。

我們不再狹隘的將節點視為動物(單體,if you prefer)，而是將節點視為「資訊」。

舉個例子：
在此題，節點0代表著「動物0屬於A」，節點1代表著「動物0屬於B」，節點2代表著「動物0屬於C」(顯然需要3倍的空間)
要怎麼做到題目要求呢？我們知道，Disjoint set維護的是連通性，而在這裡資訊之間的連通性代表的是「可互相推導」，也就是「因果關係」。
那麼，對於每個語句，如果他會讓某些不該互相推導出的資訊聯通的話就是假的，否則是真的。

大概都說破了XD，記得有些特例要特判，不然會像我一樣吃很多WA QQ。
還是沒感覺的就看code吧~

#include<cstdio>
using namespace std;
const int maxn=50000+5;
int fa[maxn*3];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
int main()
{
    int N,K,ans=0;
    scanf("%d%d",&N,&K);
    for(int i=0;i<N*3;i++) fa[i]=i;
    for(int i=0,type,a,b;i<K;i++)
    {
        scanf("%d%d%d",&type,&a,&b);a--,b--;
        if(a>=N || b>=N) {ans++;continue;}
        if(type==1)
        {
            bool flag=1;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++) if(i!=j && findset(a*3+i)==findset(b*3+j)) {flag=0;break;}
            if(!flag) {ans++;continue;}
            for(int i=0;i<3;i++) fa[findset(a*3+i)]=findset(b*3+i);
        }
        else
        {
            bool flag=1;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++) if(j!=(i+1)%3 && findset(a*3+i)==findset(b*3+j)) {flag=0;break;}
            if(!flag) {ans++;continue;}
            for(int i=0;i<3;i++) fa[findset(a*3+i)]=findset(b*3+((i+1)%3));
        }
    }
    printf("%d\n",ans);
}