题目大意
有N头牛，他们中间有些牛会认为另外一些牛“厉害”，且这种认为会传递，即若牛A认为牛B“厉害”，牛B认为牛C“厉害”，那么牛A也认为牛C“厉害”。现给出一些牛的数对(x, y)表示牛x认为牛y厉害。那么，求出所有的牛都认为该牛“厉害”的牛的个数。
题目分析
牛之间的关系，形成一个有向图。其中存在一些强连通分支，若强连通分支内的一个牛被所有牛认为“厉害”，那么整个强连通分支内的牛都被认为“厉害”。因此，将强连通分支合并为一个点，对图重构。
重构后的图为一个简单的有向图，题目转换为寻找能从所有点均可达的点的数目（实际数目为点代表的强连通分支内的点数目之和）。使用定理有向无环图中出度为0的点，可以从任何出度不为0的点到达。
因此，寻找该有向无环图中出度为0的点的个数，若出度为0的点的个数大于1，则这些出度为0的点之间互相不可达，则不存在所有点均可达的点；若出度为0的点的个数为1，则该出度为0的点代表的强连通分支内点的个数，即为题目的结果。
实现(c++)
#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
#include<algorithm> using namespace std;
#define MAX_NODE 10005
#define min(a, b) a < b? a:b vector<int> gGraph[MAX_NODE];
stack<int> gStack;
bool gVisited[MAX_NODE]; //判断点是否被访问过
bool gInStack[MAX_NODE]; //判断点是否在栈中
int gDfn[MAX_NODE]; //在DFS过程中，点第一次被访问到的时间
int gLow[MAX_NODE]; //点x下方的点所能到达的序号最小的点的序号
int gIndex; int gClusterIndex;
int gClusterOfNode[MAX_NODE]; //每个点所属的强连通分支序号 //强连通分支结构体
struct Cluster{
int cluster_id;
int node_num;
vector<int> linked_cluster;
Cluster(int id, int num) :cluster_id(id), node_num(num){};
bool LinkedCluster(int cluster){
return find(linked_cluster.begin(), linked_cluster.end(), cluster) != linked_cluster.end();
}
void LinkCluster(int cluster){
linked_cluster.push_back(cluster);
}
~Cluster(){
linked_cluster.clear();
}
}; vector<Cluster> gClusters;
//tarjan 算法求强连通分支
void Tarjan(int u){
gDfn[u] = gLow[u] = ++gIndex;
gVisited[u] = true;
gInStack[u] = true;
gStack.push(u);
for (int i = 0; i < gGraph[u].size(); i++){
int v = gGraph[u][i];
if (gVisited[v] == false){
Tarjan(v);
gLow[u] = min(gLow[u], gLow[v]);
}
else if(gInStack[v]){ //注意，需要v在栈中才可以
gLow[u] = min(gLow[u], gDfn[v]);
}
}
if (gDfn[u] == gLow[u]){
int v, num = 0;
do{
v = gStack.top();
gClusterOfNode[v] = gClusterIndex;
gStack.pop();
gInStack[v] = false; //注意恢复
num++;
} while (u != v);
gClusters.push_back(Cluster(gClusterIndex, num)); gClusterIndex++;
}
} //将强连通分支的各个点染色之后，再重新建图
void ReconstructGraph(int n){
for (int u = 1; u <= n; u++){
for (int j = 0; j < gGraph[u].size(); j++){
int v = gGraph[u][j];
int uc = gClusterOfNode[u];
int vc = gClusterOfNode[v];
if (uc != vc && !gClusters[uc].LinkedCluster(vc))
gClusters[uc].LinkCluster(vc);
}
}
}
/*
int gRoot[MAX_NODE];
int GetRoot(int c){
if (gRoot[c] != c){
gRoot[c] = GetRoot(gRoot[c]);
}
return gRoot[c];
}
void Union(int c1, int c2){
int p1 = GetRoot(c1);
int p2 = GetRoot(c2);
if (p1 != p2){
gRoot[p1] = p2;
}
} bool DAG(){ //判断一个图是否为连通图，在此题中，可以不用判断
int n = gClusters.size(); for (int i = 0; i < n; i++){
gRoot[i] = i;
} for (int u = 0; u < n; u++){
for (int i = 0; i < gClusters[u].linked_cluster.size(); i++){
int v = gClusters[u].linked_cluster[i];
Union(u, v);
}
}
int r = GetRoot(0);
for (int i = 1; i < n; i ++){
if (r != GetRoot(i)){
return false;
}
}
return true;
}
*/
int main(){
int n, m, u, v;
while (scanf("%d %d", &n, &m) != EOF){
for (int i = 0; i <= n; i++){
gGraph[i].clear();
}
for (int i = 0; i < m; i++){
scanf("%d %d", &u, &v);
gGraph[u].push_back(v);
}
gIndex = 0;
gClusterIndex = 0;
memset(gInStack, false, sizeof(gInStack));
memset(gVisited, false, sizeof(gVisited));
gClusters.clear(); //Tarjan 求强连通分支
for (int i = 1; i <= n; i++){
if (!gVisited[i]){
Tarjan(i);
}
} //重新构图
ReconstructGraph(n); /*
if (!DAG()){
printf("0\n");
continue;
}
*/
int zero_outdegree_cluster = 0, result = 0;
for (int i = 0; i < gClusterIndex; i++){
if (gClusters[i].linked_cluster.empty()){
zero_outdegree_cluster++;
result = gClusters[i].node_num;
}
}
//若重构后的图中各个点不能构成一个连通图（将有向边变为无向边之后仍不能），那么就不存在一个点可以被其他所有点可达
//而此时，图中也肯定存在多于1个点，其出度为0.
//故，只需要判断重构后的图中，出度为0的点是否为1个即可。若出度为0的点有且只有一个，则返回该“点”（实际为一个强连通分支）
//中的点的数目，否则，返回0 if (zero_outdegree_cluster > 1){
result = 0;
}
printf("%d\n", result);
}
return 0;
}