379. hide and seek

Vani and cl2 Playing hide and seek in a forest .

There are... In this forest N Houses ,M A directed road , It forms a directed acyclic graph .

The trees in the woods are very dense , Enough to block the line of sight , But looking down the road , But it has a wide view .

If from the house A Go down the road and you can reach B, So in A and B People in the can see each other .

Now? cl2 Here you are N Choose... From this house K As a hiding place , meanwhile Vani Also pick cl2 A house as a hiding place to go in and look for , To avoid being Vani See ,cl2 Ask for this K There is no path between any two hiding places .

In order to make Vani It's harder to find yourself ,cl2 Want to know the maximum number of hiding places you can choose .

Input format

The first line of input data is two integers N and M.

Next M That's ok , Two integers per line x,y, Represents a path from x To y The directed path .

Output format

Output an integer , Indicates the maximum number of hiding places that can be selected .

Data range

N≤200,M≤30000

sample input ：

7 5
1 2
3 2
2 4
4 5
4 6

sample output ：

3

Ideas ：

/*  Minimum path coverage ： For a directed acyclic graph (DAG), Use the least number of disjoint paths , Cover all points .（ Among them, disjoint means that the points are not repeated ）  Conclusion ： Minimum path point coverage （ Minimum path coverage ） =  Total points  -  The biggest match   prove ： 1. Drawing   Finding the minimum path cover uses the disassembly point , A point is divided into two points , Points and entry points are shown respectively ,  So from the point i->j Just use one side of the , From the point on the left i Connect to the right entry point j’ Express ,  The resulting graph is a bipartite graph , Because all the edges are between the left and right , There is no point inside . 2. conversion   At this point, each path in the original graph is converted to the new graph , Because the paths in the original graph do not intersect with each other , So each point has at most one out degree and one in degree ,  This means that in the new picture , Each point on the left can only be connected to one edge on the right at most , The point on the right will only have one edge connected at most , Each point can only belong to one edge at most . ① A path in the original figure <=> A set of matches in the new graph （ Each point in the new graph can only belong to one edge at most ） ② The end point of each path in the original figure （ No way out ）<=> The unmatched points on the left of the new graph  3. deduction   Find the number of disjoint paths in the original graph <=> Find the minimum number of end points of the path <=> Find the least left non matching points <=> Maximum matching   expand ：  Minimum path repeat point coverage ： On the basis of the minimum path covering problem , Remove disjoint .  Conclusion ： Original drawing G, Find the graph after transitive closure G’, be G Minimum path repeat point coverage =G’ Minimum path coverage of   In this question , Note that the minimum path repeat point coverage is cnt, The answer to this question is cnt  prove ： ①k<=cnt  this cnt This path covers all the points , So what you ask for k A point must be from here cnt Click in the path ,  And select at most one point on each path , therefore k<=cnt ②k>=cnt  structure ： take cnt The ends of all paths are put into a set E in , remember next(E) The return is from E A collection of all points that can be reached from each point in the   Classification of discussion ： i)E ∩ next(E) = Ø , here E Points within cannot reach each other , explain E All points in the are one k=cnt The plan  ii)E ∩ next(E) ≠ Ø ,  about E Any point in p, Let this point go in the opposite direction , Until this point to a not next(E-p) In the point , It can be proved that when this point reaches the starting point, it must not be next(E-p) in .  Reduction to absurdity ： If this point comes to the starting point , Still in next(E-p) in , explain p The starting point of the path can be reached by other paths , Then this path has no meaning of existence and can be omitted , Does not satisfy the minimum path repeat point coverage .  So you can also select a point in each path , Make these points unreachable in pairs , namely k=cnt */

Code ：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, M = 30010;

int n, m;
bool d[N][N], st[N];
int match[N];

bool find(int x)
{
    
    for (int i = 1; i <= n; i ++ )
        if (d[x][i] && !st[i])
        {
    
            st[i] = true;
            int t = match[i];
            if (t == 0 || find(t))
            {
    
                match[i] = x;
                return true;
            }
        }

    return false;
}

int main()
{
    
    scanf("%d%d", &n, &m);
    while (m -- )
    {
    
        int a, b;
        scanf("%d%d", &a, &b);
        d[a][b] = true;
    }

    //  Pass closures 
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] |= d[i][k] & d[k][j];

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
    
        memset(st, 0, sizeof st);
        if (find(i)) res ++ ;
    }

    printf("%d\n", n - res);

    return 0;
}