二分图

如果一张无向图的$N$个节点$(N\ge 2)$可以分成$A,B$两个非空集合，其中$A\cap B=\varnothing$,并且在同一集合内的点都没有边相连，那么成这张无向图为一张二分图。

二分图的判定

1.一张图是二分图 等价于 2.染色法不存在矛盾 等价于 3.不存在奇数环

先证明2、3的等价性：
$2\to 3$:假设存在奇数环，那么我们在环中每个点进行1、2、1、2…的染色，最后一定头尾颜色相同，染色法存在矛盾，假设不成立。
$3\to 2$:假设染色法存在矛盾，那么唯一的情况就形如以下形式：

即一定存在奇数环，假设不成立。
综上，2和3等价。

再证明1和2、3等价：
$1\to 3$:假设存在奇数环，那么在二分图中一定是以下的形式：

即同一集合内的点有边相连，该图不是二分图，假设不成立。
$2\to 1$:如果染色法不存在矛盾，那么我们可以把编号为1的点放在一个集合，编号为2的点放在一个集合，显然最后会构成一个二分图。

综上，以上1、2、3等价。

[NOIP 2010 提高组] 关押罪犯

S 城现有两座监狱，一共关押着 $N$ 名罪犯，编号分别为 $1\sim N$。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 $c$ 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 $c$ 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 $N$ 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

每行中两个数之间用一个空格隔开。第一行为两个正整数 $N,M$，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 $M$ 行每行为三个正整数 $a_j,b_j,c_j$，表示 $a_j$ 号和 $b_j$ 号罪犯之间存在仇恨，其怨气值为 $c_j$。数据保证 $1<a_j<b_j\le N,0<c_j\le 10^9$，且每对罪犯组合只出现一次。

输出格式

共一行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。

样例输入 #1

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

样例输出 #1

3512

输入输出样例说明

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 $3512$（由 $2$ 号和 $3$ 号罪犯引发）。其他任何分法都不会比这个分法更优。

数据范围

对于 $30\%$ 的数据有 $N\le 15$。

对于 $70\%$ 的数据有 $N\le 2000,M\le 50000$。

对于 $100\%$ 的数据有 $N\le 20000,M\le 100000$。

将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。
那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。

我们在 $[0,10^9]$ 之间枚举最大边权 $limit$，当 $limit$判断能否将所有点分成两组，使得所有权值大于 $limit$ 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 $limit$ 的边构成的新图是否是二分图。

为了加速算法，我们来考虑是否可以用二分枚举 $limit$， 假定最终最大边权的最小值是 $Ans$，那么当 $limit\in [ans,10^9]$时，所有边权大于 $limit$ 的边，必然是所有边权大于 $Ans$ 的边的子集，因此由此构成的新图也是二分图。
当 $limit\in [0,ans-1]$ 时，由于 $ans$ 是新图可以构成二分图的最小值，因此由大于 $limit$ 的边构成的新图一定不是二分图。
所以整个区间具有二段性，可以二分出分界点 $ans$ 的值。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010, M = 200010;
int h[N], e[M], ne[M], w[M], tot;
int color[N];
int n, m;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
bool dfs(int u, int c, int mid)
{
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (w[i] <= mid) continue;
        if (color[j])
        {
            if (color[j] == c) return false;
        }
        else if (!dfs(j, 3 - c, mid)) return false;
    }
    return true;
}
bool check(int mid)
{
    memset(color, 0, sizeof color);
    for (int i = 1; i <= n; i ++ )
    {
        if (!color[i])
            if (!dfs(i, 1, mid)) return false;
    }
    return true;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

二分图的最大匹配

任何两条边没有公共端点的边的集合称为图的一组匹配。在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。
对于任意一组匹配$S$($S$是一个边集)，属于$S$的边被称为"匹配边"，不属于$S$的边被称为"非匹配边"。匹配边的端点被称为"匹配点"，其他节点被称为“非匹配点”。如果在二分图中存在一条连接两个非匹配点的路径$path$，使得非匹配边与匹配边在$path$上交替出现，那么称$path$是匹配$S$的增广路，也称交错路。
增广路具有以下性质：
1.长度$len$是奇数。
2.路径上第$1,3,5,...,len$条边是非匹配边，第$2,4,6,...,len-1$条边是匹配边。

二分图的一组匹配$S$是最大匹配，当且仅当图中不存在$S$的增广路。
证明：前推后比较好推，假设存在增广路，那么我们可以把非匹配边变成匹配边，把匹配边变成非匹配边，这样匹配的边数还能比原先多1，所以假设不成立。
后推前比较困难，此处略。

我们求二分图最大匹配的算法的匈牙利算法

//match[j]=a,表示女孩j的现有配对男友是a
int match[N];
//st[]数组我称为临时预定数组，st[j]=a表示一轮模拟匹配中，女孩j被男孩a预定了。
int st[N];
//这个函数的作用是用来判断,如果加入x来参与模拟配对,会不会使匹配数增多
int find(int x)
{
    //遍历自己喜欢的女孩
    for(int i = h[x] ; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true;//那x就预定这个女孩了
            //如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩。配对成功,更新match
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    //自己中意的全部都被预定了。配对失败。
    return false;
}
//记录最大匹配
int res = 0;
for(int i = 1; i <= n1 ;i ++)
{  
    //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
    memset(st,false,sizeof st);
    if(find(i)) 
        res++;
}  

匈牙利算法的正确性基于贪心策略，对于左侧的$a$能够和右侧的点成功匹配，我们假设不让$a$匹配，那么最后最多只是多剩下一个右侧的点，如果右侧这个点不能再和其他左侧点匹配，那么答案总数是少了1的；假设能和其他左侧点匹配，那么最终答案总数不变，但是左侧少了一个候选点。综上，如果能匹配我们就匹配，这样一定能得到最优解。

棋盘覆盖

给定一个$N$行$N$列的棋盘，已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为 $2$、宽度为 $1$的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

输入格式
第一行包含两个整数 $N$和 $t$，其中 $t$为禁止放置的格子的数量。
接下来 $t$行每行包含两个整数 $x$和 $y$，表示位于第 $x$ 行第 $y$列的格子禁止放置，行列数从$1$开始。

输出格式
输出一个整数，表示结果。

数据范围
$1\le N\le 100,0\le t\le 100$

输入样例：

8 0

输出样例：

32

把格子看成点
把卡片看成边
则只要能放卡片的相邻两个格子就连一条边

本图是一个二分图，所有的$(i+j)\%2==0$的点是一类，$(i+j)\%2==1$是一类，显然一类之内是一定不存在边的。

问题转化为->最多取多少条边,满足卡片不重叠–所有选出的边没有公共点–二分图
放最多的牌–找到最多的边–二分图上最大匹配

#include <iostream>
#include <cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 110;
bool st[N][N], g[N][N];
PII match[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int res = 0;
int n, m;
bool find(int x, int y)
{
    for (int i = 0; i < 4; i ++ )
    {
        int a = dx[i] + x, b = dy[i] + y;
        if (a <= 0 || a > n || b <= 0 || b > n) continue;
        if (st[a][b] || g[a][b]) continue;
        PII t = match[a][b];
        st[a][b] = 1;
        if (t.x == 0 || find(t.x, t.y))
        {
            match[a][b] = {x, y};
            return true;
        }
    } 
    return false;
}
int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if ((i + j) % 2 == 0 && !g[i][j])
            {
                memset(st, 0, sizeof st);
                if (find(i, j)) res ++ ;
            }
               
    cout << res << endl;
    return 0;
}

二分图的最小点覆盖

给定一张二分图，求出一个最小的点集$S$,使得图中任意一条边都有至少一个端点属于$S$,这个问题被称为二分图的最小点覆盖问题。

二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。

证明：
1.二分图最小点覆盖包含的点数$\ge$二分图最大匹配包含的边数
因为最大匹配是二分图中所有边的一个子集，并且所有边都没有公共点，也正因此至少要在每条匹配边中选择一个端点才能将所有匹配边覆盖。

2.二分图最小点覆盖包含的点数$=$二分图最大匹配包含的边数
采用以下构造方法：
1.求二分图的最大匹配
2.从左侧每一个非匹配点出发寻找增广路径(一定不会成功，如果成功则说明1中求的不是最大匹配)，标记每一个访问过的节点。
3.取左侧未被标记的点、右侧被标记的点，就得到了二分图的最小点覆盖。
证明该构造方法的正确性：
1.左边非匹配点一定都被标记，因为我们是从左侧每一个非匹配点出发寻找增广路径的。
2.右侧非匹配点都一定没有被标记，否则的话就得到了增广路。
3.一对匹配点要么都被标记，要么都没被标记，因为在寻找增广路的过程中，左侧点只能由右侧点到达。
在构造中，我们取了左侧未被标记的点、右侧被标记的点。根据以上讨论可以发现，恰好是每条匹配边都选取了一个点，所以选出来的点数等于最大匹配包含的边数。

再来讨论这种选法是否覆盖了所有边
1.匹配边一定被覆盖了,因为恰好有一条端点被取走了。
2.不存在连接两个非匹配点的边，否则就存在长度为1的增广路了。
3.连接左部非匹配点$i$,右部匹配点$j$的边也被覆盖，左部非匹配点是起点，所以说一定可以标记$j$,所以$j$一定被选取了，所所以这条边一定被覆盖。
4.连接左部匹配点$i$,右部非匹配点$j$的边也被覆盖，右部非匹配点一定没有被标记，说明没有通过$i$到达，$i$没有被标记,所以$i$一定被选取了，所所以这条边一定被覆盖。

机器任务

有两台机器 $A，B$以及 $K$ 个任务。机器 $A$有 $N$种不同的模式（模式 $0\sim N-1$），机器 $B$有 M种不同的模式（模式 $0\sim M-1$）。两台机器最开始都处于模式 $0$。每个任务既可以在 $A$上执行，也可 以在$B$执行。对于每个任务 $i$，给定两个整数 $a[i]$和 $b[i]$，表示如果该任务在 $A$上执行，需要设置模式为 a[i]，如果在 上执行，需要模式为 $b[i]$。任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。
求怎样分配任务并合理安排顺序，能使机器重启次数最少。

输入格式
输入包含多组测试数据。

每组数据第一行包含三个整数 $N,M,K$。
接下来 $K$行，每行三个整数 $i,a[i]$和 $b[i]$，$i$ 为任务编号，从 $0$开始。
当输入一行为 $0$ 时，表示输入终止。

输出格式
每组数据输出一个整数，表示所需的机器最少重启次数，每个结果占一行。

数据范围
$N,M<100,K<100$

$0\le a[i]<N$

$0\le b[i]<M$

输入样例：

5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0

输出样例：

3

$a[i]=0||b[i]=0$时可以跳过
一个任务i可以被$A、B$机器的两种状态$a[i]、b[i]$完成，将一个任务看成一条边，两种状态看成两个端点，要完成一个任务就要从这两个点中选一个点(任务可以在$A$上执行也可以在$B$上执行)，对于所有任务就要从$N+M-2$个点中(不包含初始$0$状态)选出最少的点，覆盖所有的边(任务)，问题就变成求最小点覆盖问题。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
bool g[N][N], st[N];
int match[N];
int n, m, k;
int res;
bool find(int u)
{
    for (int i = 1; i < m; i ++ )
    {
        if (st[i] || !g[u][i]) continue;
        st[i] = 1;
        if (!match[i] || find(match[i]))
        {
            match[i] = u;
            return true;
        }
    }
    return false;
}
int main()
{
    while (cin >> n , n)
    {
        cin >> m >> k;
        memset(g, 0, sizeof g);
        memset(match, 0, sizeof match);
        res = 0;
        for (int i = 1; i <= k; i ++ )
        {
            int id, a, b;
            cin >> id >> a >> b;
            if (!a || !b) continue;
            g[a][b] = 1;
        }
        for (int i = 1; i < n; i ++ )
        {
            memset(st, 0, sizeof st);
            if (find(i)) res ++ ;
        }
        cout << res << endl;
    }
    return 0;
}

二分图最大独立集

给定一张无向图$G=(V,E)$，满足以下条件的点集$S$被称为图的独立集。
1.$S\subseteq V$
2.$\forall x,y\in S,(x,y)\notin E$
即图的独立集就是任意两点之间都没有边相连的点集。包含点数最多的一个就是图的最大独立集。

对应地，任意两点之间都有一条边相连的子图被称为无向图的“团”。点数最多的团被称为图的最大团。

无向图$G$的最大团等于其补图$G^{\prime }$的最大独立集。
正确性显然。

设$G$是有$n$个节点的二分图，$G$的最大独立集的大小等于$n$减去最大匹配数。
证明：选出最多的点构成独立集
等价于 在图中去掉最少的点，使剩下的点之间没有边
等价于 用最少的点覆盖所有的边

骑士放置

给定一个 $N\times M$ 的棋盘，有一些格子禁止放棋子。

问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。

输入格式
第一行包含三个整数 $N,M,T$，其中 $T$表示禁止放置的格子的数量。

接下来 $T$行每行包含两个整数 $x$和 $y$，表示位于第 $x$行第 $y$列的格子禁止放置，行列数从 1开始。

输出格式
输出一个整数表示结果。

数据范围
$1\le N,M\le 100$

输入样例：

2 3 0

输出样例：

4

#include <iostream>
#include <cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 110;
bool st[N][N], g[N][N];
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
PII match[N][N];
int n, m, t;
int res;

bool find(int x, int y)
{
    for (int i = 0; i < 8; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m) continue;
        if (g[a][b] || st[a][b]) continue;
        st[a][b] = 1;
        PII t = match[a][b];
        if (t.x == 0 || find(t.x, t.y))
        {
            match[a][b] = {x, y};
            return true;
        }
    }
    return false;
}
int main()
{
    cin >> n >> m >> t;
    for (int i = 1; i <= t; i ++ )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            if ((i + j) % 2 == 0 && !g[i][j])
            {
                memset(st, 0, sizeof st);
                if (find(i, j)) res ++ ;
            }
        }
    }
    cout << n * m - t - res << endl;
    return 0;
}

本图是一个二分图，所有的$(i+j)\%2==0$的点是一类，$(i+j)\%2==1$是一类，显然边只存在两类之间。
接下来，求上述二分图的最大独立集即可。

有向无环图的最小路径点覆盖

给定一张有向无环图，要求用尽量少的不相交的简单路径，覆盖有向无环图的所有顶点(也就是各个顶点恰好被覆盖一次)。这个问题被称为有向无环图的最小路径点覆盖，简称“最小路径覆盖”。

设原先的有向无环图为$G=(V,E),n=|V|$。把$G$中的每个点$x$拆成编号为$x$和$x+n$的两个点。建立一张新的二分图，$1～n$作为二分图左部点，$n+1～2n$作为二分图右部点，对于原图的每条有向边$(x,y),$，在二分图的左部点$x$与右部点$x+n$之间连边。最终得到的二分图称为$G$的拆点二分图,记为$G_2$。

有向无环图$G$的最小路径点覆盖包含的路径条数，等于$n$减去拆点二分图$G_2$的最大匹配数。

证明:
在有向无环图$G=(V,E)$的最小路径覆盖中，对于任意的$x\in V$，因为路径不相交，所以$x$的入度和出度都不超过$1$。因为每个节点都被覆盖，所以x的入度和出度至少有一个是$1$。
因此，最小路径覆盖中的所有边，在拆点二分图$G_2$中构成一组匹配。最小路径覆盖中每条边$(x,y)$的起点$x$与二分图每条匹配边$(x,y+n)$ 的左部点 $x$ 是一一对应的。
特别地，对于每条路径的终点$t$，因为$t$没有出边，所以在二分图中，$t$匹配失败。即路径的终点和二分图左部的非匹配点是一一对应的。
路径覆盖包含的路径条数最少
路径的终点数(出度为0的点数)最少二分图左部非匹配点最少
故$G$ 的最小路径覆盖的路径数等于n减去拆点二分图 $G_2$的最大匹配数。证毕。

给定一张有向无环图,要求用尽量少的可相交的简单路径,覆盖有向无环图的所有顶点(也就是一个节点可以被覆盖多次)。这个问题被称为有向无环图的最小路径可重复点覆盖。
在最小路径可重复点覆盖中，若两条路径$\dots \to u\to p\to v\to .$和$.\to x\to p\to y\to \dots$ 在点 $p$相交,则我们在原图中添加一条边$(x,y)$,让第二条路径直接走 $x\to y$,就可以避免重复覆盖点$p$。
进一步地，如果我们把原图中所有间接连通的点对$x,y$直接连上有向边$(x,y)$,那么任何“有路径相交的点覆盖”一定都能转化成“没有路径相交的点覆盖”。
综上所述,有向无环图$G$的最小路径可重复点覆盖,等价于先对有向图传递闭包，得到有向无环图 $G^{\prime }$，再在$G^{\prime }$上求一般的(路径不可相交的)最小路径点覆盖。

捉迷藏

$Vani$ 和 $cl2$ 在一片树林里捉迷藏。

这片树林里有$N$座房子，$M$条有向道路，组成了一张有向无环图。

树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。

如果从房子 $A$ 沿着路走下去能够到达 $B$，那么在 $A$和 $B$里的人是能够相互望见的。现在 $cl2$ 要在这 N座房子里选择 K座作为藏身点，同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找，为了避免被 $Vani$ 看见，$cl2$ 要求这 $K$个藏身点的任意两个之间都没有路径相连。为了让 $Vani$ 更难找到自己，$cl2$ 想知道最多能选出多少个藏身点。

输入格式
输入数据的第一行是两个整数$N$和$M$。接下来$M$行，每行两个整数 $x,y$，表示一条从$x$到 $y$的有向道路。

输出格式
输出一个整数，表示最多能选取的藏身点个数。

数据范围
$N\le 200,M\le 30000,1\le x,y\le N$。

输入样例：

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

输出样例：

3

最小路径$cnt$条重复点覆盖
答案$==cnt$
则需证$\le cnt$
和$=cnt$
证$\le cnt$
由于$cnt$条路径把所有点全覆盖了
1 所以选$k$个点从这$cnt$条路径上选
2 每条路径上不能选$\ge 2$个点 最多只能选$1$个点
否则一条路径上前面的点一定能看到后面的点(矛盾)
3 则答案必然$\le cnt$(最多$cnt$条路线,每条路线最多选$1$个,最多选$cnt$个点)

证$\ge cnt$
构造:
$cnt$条路线的$cnt$个终点放到集合E中
找一下这个$E$里面 每一个终点 所有可以到的点
$next(E)$ : 从$E$中每个点出发可以到达所有点的集合

1. 如果$E$和$next(E)$无交集 说明$E$内的点两两之间不能互相到达 说明E中所有点就是一种方案$(k=cnt)$

2. 如果$E$和$next(E)$有交集
   我们让终点$E[i]$沿有向边倒着走,走到$E[i]$不属于$next(E)$为止,直到做到$E$和$next(E)$没有交集为止

   最多走到起点能达到$E$和$next(E)$没有交集

   反证:
   假设一直往前退到起点都不能保证$E[i]$不属于$next(E)$
   则说明$E[i]$所在的起点(其他点都能被间接到达)都是$E$中所有终点(其他路径)能到达的
   那这条路径就没有存在的价值了
   可以找到能到达$E[i]$的路径$path$,把当前$E[i]$接到$path$后
   $E[i]$作为起点的路径上的所有点都可以被覆盖,总路径数$cnt-1$
   这就和$cnt$是最小路径重复点覆盖矛盾

所以答案就是$cnt$

#include <iostream>
#include <cstring>
using namespace std;
const int N = 210, M = 30010;
bool st[N], d[N][N];
int match[N];
int res = 0;
int n, m;
bool find(int u)
{
    for (int i = 1; i <= n; i ++ )
    {
        if (!d[u][i] || st[i]) continue;
        st[i] = 1;
        if (!match[i] || find(match[i]))
        {
            match[i] = u;
            return true;
        }
    }
    return false;
}
int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        d[a][b] = 1;
    }
    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];
            }
    for (int i = 1; i <= n; i ++ )
    {
        memset(st, 0, sizeof st);
        if (find(i)) res ++ ;
    }
    cout << n - res << endl;
    return 0;
}