题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3861

好题，同时检测 Tarjan 模板和 Hungry 模板。

题目大意：一个有向图，让你按规则划分区域，要求划分的区域数最少。

规则如下：

1、有边u到v以及有边v到u，则u，v必须划分到同一个区域内。

2、一个区域内的两点至少要有一方能到达另一方。

3、一个点只能划分到一个区域内。

解题思路：

根据规则1可知必然要对强连通分量进行缩点，缩点后变成了一个弱连通图。

根据规则2、3可知即是要求图的最小路径覆盖。

定义:

最小路径覆盖：在图中找一些路径（路径数最少），使之覆盖了图中所有的顶点，且每个顶点有且仅和一条路径有关联。

最小顶点覆盖：在图中找一些点（顶点数最少），使之覆盖了图中所有的边，每条边至少和一个顶点有关联。

二分图：最小顶点覆盖=最大匹配数。最小路径覆盖=顶点数-最大匹配数。 

/*
 * Author: Haipz
 * School: HDU
 * File Name: 3861.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

const int N = 5000, M = 100000;
int first[N + 5], girst[N + 5];
struct edge {
    int v, pre;
} f[M + 5], g[M + 5];
int low[N + 5], dfn[N + 5];
int belong[N + 5], inStack[N + 5], Stack[N + 5];
int top, index, bcnt;

void addEdge(int k, int u, int v) {
    f[k].v = v, f[k].pre = first[u], first[u] = k;
    return;
}

void _addEdge(int k, int u, int v) {
    g[k].v = v, g[k].pre = girst[u], girst[u] = k;
    return;
}

void Tarjan(int u) {
    Stack[top++] = u, inStack[u] = 1;
    low[u] = dfn[u] = ++index;
    for (int i = first[u]; i; i = f[i].pre) {
        int v = f[i].v;
        if (dfn[v] == 0) {
            Tarjan(v);
            low[u] = min(low[v], low[u]);
        } else if (inStack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]){
        ++bcnt;
        int v;
        do {
            v= Stack[--top];
            inStack[v] = 0;
            belong[v] = bcnt;
        } while( u!=v );
    }
}

void init(int n) {
    top = bcnt = index = 0;
    for (int i = 1; i <= n; ++i) belong[i] = i;
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    memset(inStack, 0, sizeof(inStack));
    return;
}

bool vis[N + 5];
int link[N + 5];

bool find(int x) {
    for (int i = girst[x]; i; i = g[i].pre)
        if (!vis[g[i].v]) {
            vis[g[i].v] = true;
            if (link[g[i].v] == -1 || find(link[g[i].v])) {
                link[g[i].v] = x;
                return true;
            }
        }
    return false;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        init(n);
        memset(first, 0, sizeof(first));
        for (int i = 1; i <= m; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            addEdge(i, u, v);
        }
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) Tarjan(i);
        memset(girst, 0, sizeof(girst));
        m = 0;
        for (int i = 1; i <= n; ++i) {
            int u = belong[i];
            for (int j = first[i]; j; j = f[j].pre) {
                int v = belong[f[j].v];
                if (u != v) _addEdge(++m, u, v);
            }
        }
        memset(link, -1, sizeof(link));
        int key = 0;
        for (int i = 1; i <= bcnt; ++i) {
            memset(vis, false, sizeof(vis));
            if (find(i)) ++key;
        }
        printf("%d\n", bcnt - key);
    }
    return 0;
}

转载保留版权：http://haipz.com/blog/i/5714 - 海胖博客