[POJ 1182]食物链

可以看出，我們永遠不會知道特定的某隻動物是$A$、$B$或$C$

為了方便說明，令$S_{i}$為第$i$隻動物

因此，我們只能對於$S_{i}$做出$S_{i}=A$、$S_{i}=B$或者$S_{i}=C$假設
當某個假設可以推到另一個假設，我們就將這兩個假設連邊，剛好在這題，如果$A$可以推到$B$，那麼$B$也可以推到$A$，因此可以直接連無向邊
再仔細想想，可以知道如果$X$吃$X$的情況出現，若且唯若可以從$S_{i}=A$的假設推到$S_{i}\neq A$的假設，也就是這兩個假設在同一個連通塊裡面

我們只要判斷連通性就好了，可以用並查集來維護！

如果上面的題解仔細看了好幾遍還是沒有頭緒，請參考code

時間複雜度：$O(K\alpha(N))$ (不過code裡面的並查集是$O(\log N)$)

p.s. POJ的測資結尾竟然還有其他數字！所以如果你是做重複輸入的，會莫名地得到WA，需要在code裡面加上那個break才能通過Orz

code:

#include<cstdio>
#include<cassert>
using namespace std;
//void assert(bool valid){if(valid)return;for(int a=0,b=0;;)a/=b;}
struct Djset
{
    int s[150000];
    void clear(const int n){for(int i=0;i<n;i++)s[i]=i;}
    int find(const int a){return s[a]==a?a:(s[a]=find(s[a]));}
    bool merge(int a,int b){if((a=find(a))==(b=find(b)))return false;s[a]=b;return true;}
    int operator[](const int i){return find(i);}
}DJ;
int N,K;
int main()
{
    while(scanf("%d%d",&N,&K)==2)
    {
        DJ.clear(N*3);
        int ans=0;
        for(int i=0,d,a,b;i<K;i++)
        {
            scanf("%d%d%d",&d,&a,&b),a--,b--;
            assert(a>=0&&b>=0);
            if(a>=N||b>=N)ans++;
            else if(d==1)
            {
                if(DJ[a]==DJ[N+b]||DJ[a]==DJ[N+N+b])ans++;
                else for(int j=0;j<3;j++)DJ.merge(N*j+a,N*j+b);
            }
            else if(d==2)
            {
                if(DJ[a]==DJ[b]||DJ[a]==DJ[N+N+b])ans++;
                else for(int j=0;j<3;j++)DJ.merge(N*j+a,N*((j+1)%3)+b);
            }
            else assert(0);
        }
        printf("%d\n",ans);
        break;
    }
    return 0;
}