本文共 3601 字，大约阅读时间需要 12 分钟。
在一个缩短森林（即图的强连通分量的缩影森林）中，每个缩影点代表多个原始点。问题要求找出被所有牛崇拜的牛的数量。根据问题描述，缩影点的出度为0时可能存在被所有牛崇拜的牛。具体来说，如果存在多个出度为0的缩影点，则这些点对应的牛不会互相崇拜，从而不存在被所有牛崇拜的牛。
因此，我们需要计算出出度为0的缩影点的数量，这些点对应的牛即为被所有牛崇拜的牛。
为了解决这个问题，我们采用了基于Tarjan算法的图遍历方法，具体步骤如下：
图的表示：使用邻接表表示图，其中每个节点包含其目标点和下一个边指针。
Tarjan算法：通过深度优先搜索（DFS）遍历图，计算每个节点的dfn（ discovery time）和low值（ low value），并进行强连通分量的缩影森林分析。
颜色标记：将每个强连通分量中的节点赋予不同的颜色。颜色数即为强连通分量的数量。
出度计算：遍历所有边，统计每个颜色类别的出度。如果某个颜色类别的出度为0，则该颜色类别的节点是出度为0的缩影点。
结果计算：统计出度为0的颜色类别数量，即为被所有牛崇拜的牛的数量。如果有多个出度为0的颜色类别，则返回0，否则返回该颜色类别的节点数量。
#include#include #include using namespace std;class Graphics {private: struct Edge { int to, next; } edge[MAXM]; struct Point { int dfn, low, color; } point[MAXN]; int sign, dfnNum, colorNum, sumOfPoint, first[MAXN]; bool vis[MAXN]; stack stk; void tarjan(int u) { point[u].dfn = ++dfnNum; point[u].low = dfnNum; vis[u] = true; stk.push(u); for (int i = first[u]; i != -1; i = edge[i].next) { int to = edge[i].to; if (!point[to].dfn) { tarjan(to); point[u].low = min(point[to].low, point[u].low); } else if (vis[to]) { point[u].low = min(point[to].dfn, point[u].low); } } if (point[u].dfn == point[u].low) { vis[u] = false; point[u].color = ++colorNum; count[colorNum] ++; while (stk.top() != u) { vis[stk.top()] = false; point[stk.top()].color = colorNum; count[colorNum] ++; stk.pop(); } stk.pop(); } } void clear(int n) { sign = dfnNum = colorNum = 0; for (int i = 1; i <= n; ++i) { first[i] = -1; vis[i] = false; count[i] = 0; } sumOfPoint = n; while (!stk.empty()) stk.pop(); } void addEdgeOneWay(int u, int v) { if (sign >= MAXM) return; edge[sign].to = v; edge[sign].next = first[u]; first[u] = sign++; } void addEdgeTwoWay(int u, int v) { addEdgeOneWay(u, v); addEdgeOneWay(v, u); } void tarjanAllPoint() { for (int i = 1; i <= sumOfPoint; ++i) { if (!point[i].dfn) { tarjan(i); } } } int getAns() { int ans = 0, ans2 = 0; int *outdegree = new int[sumOfPoint + 1]; for (int i = 1; i <= sumOfPoint; ++i) { outdegree[i] = 0; } tarjanAllPoint(); for (int i = 1; i <= sumOfPoint; ++i) { for (int j = first[i]; j != -1; j = edge[j].next) { int to = edge[j].to; if (point[to].color != point[i].color) { outdegree[point[i].color]++; } } } for (int i = 1; i <= colorNum; ++i) { if (!outdegree[i]) { ans++; ans2 = count[i]; } } delete[] outdegree; return ans == 1 ? ans2 : 0; }};Graphics graph;int main() { int n, m; scanf("%d%d", &n, &m); graph.clear(n); while (m--) { int a, b; scanf("%d%d", &a, &b); graph.addEdgeOneWay(a, b); } printf("%d\n", graph.getAns()); return 0;}
图的表示：使用邻接表edge数组和first数组表示图的边。first[u]记录节点u的第一个边的索引。
Tarjan算法：tarjan(int u)函数用于进行深度优先搜索，计算节点u的dfn和low值，并进行强连通分量的缩影森林分析。
颜色标记：在发现强连通分量时，赋予该分量的所有节点相同的颜色，并统计颜色数。
出度计算：通过遍历所有边，统计每个颜色类别的出度。出度为0的颜色类别对应出度为0的缩影点。
结果计算：统计出度为0的颜色类别数量。如果有多个，则返回0，否则返回该颜色类别的节点数。
转载地址：http://uyxfk.baihongyu.com/