有N(N<=10000)头牛，每头牛都想成为most poluler的牛，给出M(M<=50000)个关系，如(1,2)代表1欢迎2，关系可以传递，但是不可以相互，即1欢迎2不代表2欢迎1，但是如果2也欢迎3那么1也欢迎3.
给出N,M和M个欢迎关系，求被所有牛都欢迎的牛的数量。
用强联通分量做
首先求出联通分量的个数，然后依次求各个联通分量的出度，如果仅有一个连通分量出度为0则这个联通分量内的点的个数就是答案； 所以在用KO算法的时候还要判短是否这个最后的连通分量都可达
KO算法
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_V = ;
int V; // 顶点数
vector<int> G[MAX_V]; // 图的邻接表表示
vector<int> rG[MAX_V]; // 把边反向后的图
vector<int> vs; // 后序遍历顺序的顶点列表
bool used[MAX_V]; // 访问标记
int cmp[MAX_V]; // 所属强连通分量的拓扑序322 第 4 章 登峰造极——高级篇
void add_edge(int from, int to)
{
G[from].push_back(to);
rG[to].push_back(from);
}
void dfs(int v)
{
used[v] = true;
for (int i = ; i < G[v].size(); i++)
{
if (!used[G[v][i]]) dfs(G[v][i]);
}
vs.push_back(v);
}
void rdfs(int v, int k)
{
used[v] = true;
cmp[v] = k;
for (int i = ; i < rG[v].size(); i++)
{
if (!used[rG[v][i]]) rdfs(rG[v][i], k);
}
}
int scc()
{
memset(used, , sizeof(used));
vs.clear();
for (int v = ; v < V; v++)
{
if (!used[v]) dfs(v);
}
memset(used, , sizeof(used));
int k = ;
for (int i = vs.size() - ; i >= ; i--)
{
if (!used[vs[i]]) rdfs(vs[i], k++);
}
return k;
} int main( )
{
int n,m;
scanf("%d%d",&n,&m);
V=n;
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
u-- ; v-- ;
add_edge(u,v);
}
n=scc();
int u=-,ans=,fa=;
for(int i= ; i<V ; i++)
{
if(cmp[i]==n-)///最后一个拓扑序
{ u=i;
ans++;
}
}
///检查是否从所有点可达
memset(used,false,sizeof(used));
rdfs(u,);//在跑一遍dfs,利与之后判断可达
for(int i= ; i<V ; i++)
{
if(!used[i])
{
ans=;
break;
}
}
if(fa==)
printf("%d\n",ans);
else
puts("");
}
TA算法
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
using namespace std;
#define M 1000009
vector<int> edge[M];
stack<int> ss;
int n,m,tot,scc;
int low[M],DFN[M],belong[M];
int out[M],num[M];
bool instack[M];
void init()
{
for(int i = ;i < n;i++)
{
edge[i].clear();
}
tot = ;
scc = ;
while(!ss.empty()) ss.pop();
memset(low,,sizeof(low));
memset(DFN,,sizeof(DFN));
memset(out,,sizeof(out));
memset(belong,,sizeof(belong));
}
void add_edge(int u,int v)
{
edge[u].push_back(v);
}
void tarjan(int u)
{
instack[u] = true;
low[u] = DFN[u] = ++tot;
ss.push(u); //将刚访问的节点入栈
for(int i = ;i < edge[u].size();i++)
{
int v = edge[u][i];
if(!DFN[v]) //没有被访问过
{ // (不能写成不在栈中，因为在栈中的一定是访问过的，但是不在栈中的也可能访问过，只是已经划入之前的强连通分量了)
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(instack[v]) // 指向栈中节点的后向边
{
low[u] = min(low[u],DFN[v]);
}
}
if(DFN[u] == low[u]) // u 为一个强连通分量的根
{
scc++;//强连通分量的编号
int v;
do
{
v = ss.top();
ss.pop();
belong[v] = scc; //标记每个节点所在的强连通分量
num[scc]++; //每个强连通分量的节点个数
}while(u != v);
}
}
int main( )
{
init();
scanf("%d%d",&n,&m);
for(int i= ; i<m ; i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u-,v-);
}
for(int i= ; i<n ; i++)
{
if(!DFN[i])
tarjan(i);
} for(int i= ; i<n ; i++)
{
for(int j= ; j<edge[i].size() ; j++)
{
int v=edge[i][j];
if(belong[i]!=belong[v])
out[belong[i]]++;//出度
}
}
int sum=;
int ans=;
for(int i= ; i<=scc ; i++)
{
if(!out[i])//答案在出度为0的连通分量
{
sum++;
ans = num[i];///这个连通分量的数目
}
}
if(sum==)///肯定只有一个，因为假设有两个的话，这两个不可能是连通的
printf("%d\n",ans);
else
printf("0\n"); }