C - 食物鍊

來源poj1182

動物王國中有三類動物A,B,C，這三類動物的食物鍊構成了有趣的環形。A吃B， B吃C，C吃A。

現有N個動物，以1－N編号。每個動物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。

有人用兩種說法對這N個動物所構成的食物鍊關系進行描述：

第一種說法是"1 X Y"，表示X和Y是同類。

第二種說法是"2 X Y"，表示X吃Y。

此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。

1） 目前的話與前面的某些真的話沖突，就是假話；

2） 目前的話中X或Y比N大，就是假話；

3） 目前的話表示X吃X，就是假話。

你的任務是根據給定的N（1 <= N <= 50,000）和K句話（0 <= K <= 100,000），輸出假話的總數。

Input

第一行是兩個整數N和K，以一個空格分隔。

以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。

若D=1，則表示X和Y是同類。

若D=2，則表示X吃Y。

Output

隻有一個整數，表示假話的數目。

Sample Input

100 7

1 101 1

2 1 2

2 2 3

2 3 3

1 1 3

2 3 1

1 5 5

Sample Output

3

并查集，[https://www.cnblogs.com/haoabcd2010/p/5688902.html]

比較重要的是在壓縮路徑的時候要怎麼算出他們中間的關系

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iomanip>
#include<cmath>
#include<float.h> 
#include<string.h>
#include<algorithm>
#define sf scanf
#define pf printf
#define mm(x,b) memset((x),(b),sizeof(x))
#include<vector>
#include<queue>
#include<stack>
#include<map>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
typedef long long ll;
const ll mod=1e9+100;
const double eps=1e-8;
using namespace std;
const double pi=acos(-1.0);
const int inf=0xfffffff;
const int N=50005; 
int f[N],r[N];
int find(int x)
{
    int fx=x;
    if(f[x]!=x)
    {
        fx=find(f[x]);
        r[x]=(r[f[x]]+r[x])%3;
        f[x]=fx;
    }
    return f[x];
}
bool Union(int d,int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fy!=fx)
    {
        f[fy]=fx;
        r[fy]=(3-r[y]+r[x]+d-1)%3;
        return true;
    }
    if((3-r[x]+r[y])%3==d-1) return true;
    return false;
}
int main() 
{
    int n,k;
    cin>>n>>k;
    rep(i,0,N)
    {
        f[i]=i;r[i]=0;
    }
    int ans=0;
    int d,x,y;
    while(k--)
    {
        sf("%d%d%d",&d,&x,&y);
        if(x>n||y>n||(d==2&x==y)){ ans++;continue;}
        if(!Union(d,x,y)) ans++;
    }
    pf("%d",ans);
    return 0;
}
           

轉載于:https://www.cnblogs.com/wzl19981116/p/9438960.html