HAOI2006受欢迎的牛：SCC分解与应用

在分析“受欢迎的牛”问题时，如果存在一个节点x满足给定条件，那么x所在的强连通分量（SCC）同样满足这一条件。此外，合法的SCC数量最多为1，因为如果存在两个或更多满足条件的SCC，它们之间的关系应当是传递的，理论上可以通过合并这些SCC来简化问题。

解决这个问题的一种方法是首先对图进行拓扑排序，然后对排序后的图进行缩点处理。在这个过程中，可能成为答案的SCC必定是最后一个被处理的SCC，这是因为只有这样的SCC没有指向其他任何SCC的边，符合题目中关于“受欢迎”的定义。

#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;
const int maxn = 1e4 + 6;
int V;
vector G[maxn];
vector rG[maxn];
vector vs; // 后续遍历顺序
bool used[maxn];
int cmp[maxn]; // 所属强连通分量编号

void addEdge(int u, int v) {
    G[u].push_back(v);
    rG[v].push_back(u);
}

void dfs(int u) {
    used[u] = true;
    for (int i = 0; i         if (!used[G[u][i]]) dfs(G[u][i]);
    }
    vs.push_back(u);
}

void rDfs(int u, int k) {
    used[u] = true;
    cmp[u] = k;
    for (int i = 0; i         if (!used[rG[u][i]]) rDfs(rG[u][i], k);
    }
}

int scc() {
    fill(used, used + maxn, false);
    vs.clear();
    for (int i = 1; i <= V; ++i) {
        if (!used[i]) dfs(i);
    }
    fill(used, used + maxn, false);
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; --i) {
        if (!used[vs[i]]) rDfs(vs[i], ++k);
    }
    return k;
}

int n, m;
int main() {
    scanf("%d %d", &n, &m);
    V = n;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    n = scc();

    int u = 1, num = 0;
    for (int i = 1; i <= V; ++i) {
        if (cmp[i] == n) {
            u = i;
            num++;
        }
    }

    fill(used, used + maxn, false);
    rDfs(u, 0);
    for (int i = 1; i <= V; ++i) {
        if (!used[i]) {
            num = 0;
            break;
        }
    }
    printf("%d\n", num);
}

以上代码首先实现了添加边的功能，接着通过两次深度优先搜索（DFS）来寻找所有的强连通分量，并对其进行标记。最终，程序检查最后一个被标记的强连通分量是否满足题目要求，并输出符合条件的节点数量。