本文共 3704 字，大约阅读时间需要 12 分钟。

解决POJ问题2186：被所有牛崇拜的牛的数量

问题背景

在一个缩短森林（即图的强连通分量的缩影森林）中，每个缩影点代表多个原始点。问题要求找出被所有牛崇拜的牛的数量。根据问题描述，缩影点的出度为0时可能存在被所有牛崇拜的牛。具体来说，如果存在多个出度为0的缩影点，则这些点对应的牛不会互相崇拜，从而不存在被所有牛崇拜的牛。

因此，我们需要计算出出度为0的缩影点的数量，这些点对应的牛即为被所有牛崇拜的牛。

解决方案

为了解决这个问题，我们采用了基于Tarjan算法的图遍历方法，具体步骤如下：

代码实现

#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;
}
      
     
    
   

代码解释

转载地址：http://uyxfk.baihongyu.com/