题目大意：给出一张有向图，要求你将这些点进行划分，划分依据如下 1.如果两个点互相可达，那么这两个点必须在一个集合中 2.同一个集合中任意两个点u,v要满足，要么u能到达v，要么v能到达u 3.一个点只能被划分到一个集合
问最少能划分成几个点集
解题思路：首先先求出所有的强连通分量，满足条件1 满足条件2，3的话，就要求出最小路径覆盖 所以可以将所有的强连通分量进行缩点，桥作为连接，然后匈牙利一下，求出最大匹配数，再用强连通分量的数量-最大匹配数，就是答案了
Edge{int to, next;}E[M];struct Node {int x, y;}node[M];int head[N], sccno[N], pre[N], lowlink[N], stack[N], link[N];int n, m, tot, scc_cnt, dfs_clock, top;bool vis[N];void AddEdge(int u, int v) {E[tot].to = v;E[tot].next = head[u];head[u] = tot++;}void init() {scanf(“%d%d”, &n, &m);memset(head, -1, sizeof(head));tot = 0;for (int i = 1; i <= m; i++) {scanf(“%d%d”, &node[i].x, &node[i].y);AddEdge(node[i].x, node[i].y);}}void dfs(int u) {pre[u] = lowlink[u] = ++dfs_clock;stack[++top] = u;for (int i = head[u]; i != -1; i = E[i].next) {int v = E[i].to;if (!pre[v]) {dfs(v);lowlink[u] = min(lowlink[v], lowlink[u]);}else if(!sccno[v]) {lowlink[u] = min(lowlink[u], pre[v]);}}int x;if (lowlink[u] == pre[u]) {++scc_cnt;while (1) {x = stack[top–];sccno[x] = scc_cnt;if (x == u)break;}}}bool dfs2(int u) {for (int i = head[u]; i != -1; i = E[i].next) {int v =E[i].to;if (!vis[v]) {vis[v] = true;if (link[v] == -1 || dfs2(link[v])) {link[v] = u;return true;}}}return false;}void solve() {memset(pre, 0, sizeof(pre));memset(sccno, 0, sizeof(sccno));scc_cnt = top = dfs_clock = 0;for (int i = 1; i <= n; i++)if (!pre[i])dfs(i);memset(head, -1, sizeof(head));tot = 0;int u, v;for (int i = 1; i <= m; i++) {u = sccno[node[i].x];v = sccno[node[i].y];if (u != v) AddEdge(u, v);}int ans = 0;memset(link, -1, sizeof(link));for (int i = 1; i <= scc_cnt; i++) {memset(vis, 0, sizeof(vis));if (dfs2(i)) ans++;}printf(“%d\n”, scc_cnt – ans);}int main() {int test;scanf(“%d”, &test);while (test–) {init();solve();}return 0;}
，世上最累人的事，莫过於虚伪的过日子
