Cow sequencing problem

One   Original problem description

3275 -- Ranking the Cowshttp://poj.org/problem?id=3275

Two   Input and output

1  Input

The first 1 Line contains two integers  N  and  M. The first 2  To  M+1  That's ok , Each line contains two integers  X  and  Y.X  and  Y  It's all in 1  To  N  Within the scope of , A cow  X  Ranking higher than cows  Y.

2  Output

At least how many relationships must be investigated for single row output to complete the whole sorting .

3  sample input

5 5

2 1

1 5

2 3

1 4

3 4

4  sample output

3

3、 ... and   Algorithm analysis and Design

1  According to the input sample , Create a directed graph

2  According to Transitivity , Got 7 Kind of relationship , Namely

1>4

1>5

2>1

2>3

2>4

2>5

3>4

3  For having n Graph of nodes , The relationship between two people has  n(n-1)/2  Kind of ,5 Nodes share 10 Kind of relationship , Also need to know 10-7 = 3  Kind of relationship .

You can use  bitset  operation , Use one for each node  bitset  To describe .

bitset<maxn> p[maxn]; // maxn  Number of digits ,p[]  Represents a binary array

Initialization time ,p[i][i]=1, namely  p[i]  Of the  i  Position as 1（ Number from the right 0 position , The first 1 position , The first 2 position ）.

Input 1-5, Give Way  p[1][5] = 1（ The first 1 The milk yield of a cow is greater than that of the 5 head ）, be  p[1]=...100010

Input 1-4, Give Way  p[1][4] = 1（ The first 1 The milk yield of a cow is greater than that of the 4 head ）, be  p[1]=...110010

Input 2-1, Give Way  p[2][1] = 1（ The first 2 The milk yield of a cow is greater than that of the 1 head ）, be  p[2]=...000110

Input 2-3, Give Way  p[2][3] = 1（ The first 2 The milk yield of a cow is greater than that of the 3 head ）, be  p[2]=...001110

Input 3-4, Give Way  p[3][4] = 1（ The first 3 The milk yield of a cow is greater than that of the 4 head ）, be  p[3]=...011000

Determine each bit of each array , The following logic exists

if(p[i][j]){
    p[i] = p[i]|p[j]; //  Bitwise OR operation ,i  Cows produce more milk than  j  The milk yield of a cow , therefore  j  The milk production relationship between cows and other cows can be passed on to  i, So use or relation 
}

for example ：p[2][1]=1, be  p[2]=p[2]|p[1]=001110|110010=111110, cow 2 And cows 1 It matters , Then cow 1 To the cows 2.

In this way , You can find the relationship between each point and other points . use  ans  Accumulate each array element 1  The number of , Because when initializing, you can set yourself to 1, So forget it  n  Kind of relationship , Need to subtract .

Four   Code

package graph;

import java.util.BitSet;
import java.util.Scanner;

public class POJ3275 {
    public static void main(String[] args) {
        int n, m;
        Scanner scanner = new Scanner(System.in);
        // n  Head ox 
        n = scanner.nextInt();
        // m  A relationship 
        m = scanner.nextInt();
        
        BitSet p[] = new BitSet[n + 1];
        for (int i = 1; i <= n; i++) {
            p[i] = new BitSet(n + 1);
        }

        for (int i = 1; i <= n; i++)
            p[i].set(i);
        while (m-- != 0) {
            int u, v;
            u = scanner.nextInt();
            v = scanner.nextInt();
            p[u].set(v);
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                if (p[i].get(k))
                    p[i].or(p[k]);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[i].get(j)) {
                    ans++;
                }
            }
        }
        System.out.println(n * (n - 1) / 2 - ans + n);
    }
}

5、 ... and   test

Green is the input , White is the output