POJ 1182: food chain (parallel search) [easy to understand]

Hello everyone , I meet you again , I'm the king of the whole stack .

The food chain

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 43526		Accepted: 12679

Description

There are three kinds of animals in the animal kingdom A,B,C, The food chain of these three kinds of animals forms an interesting ring .A eat B, B eat C,C eat A.

existing N Animals , With 1－N Number .

Every animal is A,B,C One of the , But we don't know what kind it is . There are two ways of saying it N Describe the food chain relationship formed by animals ： The first is ”1 X Y”, Express X and Y It's the same kind .

Another way of saying it ”2 X Y”. Express X eat Y. This man is right N Animals . Use the two statements above . Say... Sentence by sentence K Sentence . this K Some sentences are true . Some are fake .

When a sentence satisfies one of the following three , This is a lie , Otherwise, it's the truth . 1） The current words conflict with some of the real words in front . It's a lie ; 2） In the current conversation X or Y Than N Big . It's a lie . 3） The current words mean X eat X, It's a lie . Your task is based on the given N（1 <= N <= 50,000） and K Sentence （0 <= K <= 100,000）, The total number of output lies .

Input

The first line is two integers N and K, Separated by a space .

below K Each row is three positive integers D,X,Y. Separate the two numbers with a space . among D The type of statement . if D=1, said X and Y It's the same kind . if D=2, said X eat Y.

Output

There is only one integer . The number of lies .

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

Copy

Sample Output

3

Copy

ok ..

This article is indeed the most specific .. Click to open the link

After reading it, I have a deeper understanding of union search ...

Weak food would like to thank the blogger ..

Also, I made a mistake when I used multiple input for this problem ..

It took me a long time ..

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<sstream>
#include<cmath>

using namespace std;

#define M 100500

int n;
int k;
int d;
int x;
int y;
int p[M];
int r[M];
int ans;

void start()
{
    for(int i=1; i<=n; i++)
    {
        p[i]=i;  // Initialize and query set 
        r[i]=0; // On initialization . Each element as a set , Its element is 1
    }
}

int find(int x)   // And look up the collection find
{
    if( p[x]==x )
        return x;
    else
    {
        int t = p[x];
        p[x] = find ( p[x] );
        r[x] = (r[x]+r[t])%3;
        return p[x];
    }
}

void Kruskal(int x, int y, int d)
{
    int xx = find(x);
    int yy = find(y);
    p[yy] = xx;
    r[yy] = (r[x]-r[y]+3+(d-1))%3;
}

int main()
{
    scanf("%d%d", &n, &k);
    start();
    ans = 0;
    for(int i=1; i<=k; i++)
    {
        scanf("%d%d%d", &d, &x, &y);
        if(x>n || y>n || (d==2&&x==y))
            ans++;
        else if( find(x) == find(y) )
        {
            if( d==1 && r[x]!=r[y] )
                ans++;
            if( d==2 && (r[x]+1)%3 != r[y] )
                ans++;
        }
        else
            Kruskal(x, y, d);
    }
    printf("%d\n", ans);
    return 0;
}

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116605.html Link to the original text ：https://javaforall.cn