参考资料:
[1]:挑战程序设计竞赛
题意:
每头牛都想成为牛群中的红人。
给定N头牛的牛群和M个有序对(A, B),(A, B)表示牛A认为牛B是红人;
该关系具有传递性,所以如果牛A认为牛B是红人,牛B认为牛C是红人,那么牛A也认为牛C是红人。
不过,给定的有序对中可能包含(A, B)和(B, C),但不包含(A, C)。
求被其他所有牛认为是红人的牛的总数。
分析(摘抄自挑战程序设计竞赛):
考虑以牛为顶点的有向图,对每个有序对(A, B)连一条从 A到B的有向边;
那么,被其他所有牛认为是红人的牛对应的顶点,也就是从其他所有顶点都可达的顶点。
虽然这可以通过从每个顶点出发搜索求得,但总的复杂度却是O(NM),是不可行的,必须要考虑更为高效的算法。
假设有两头牛A和B都被其他所有牛认为是红人,那么显然,A被B认为是红人,B也被A认为是红人;
即存在一个包含A、B两个顶点的圈,或者说,A、B同属于一个强连通分量。
反之,如果一头牛被其他所有牛认为是红人,那么其所属的强连通分量内的所有牛都被其他所有牛认为是红人。
由此,我们把图进行强连通分量分解后,至多有一个强连通分量满足题目的条件。
而按前面介绍的算法进行强连通分量分解时,我们还能够得到各个强连通分量拓扑排序后的顺序;
唯一可能成为解的只有拓扑序最后的强连通分量。
所以在最后,我们只要检查这个强连通分量是否从所有顶点可达就好了。
该算法的复杂度为O(N+M),足以在时限内解决原题。
对红色字体的理解:
满足条件的强连通分量的特点是(红牛所在的强连通分量):
(1)出度为0
(2)其余的节点都会间接或直接的指向此强连通分量的任一节点
再结合向量vs 的作用,在Dfs( )中,vs中存储的第一个节点肯定是满足条件的强连通分量中的某一节点;
在vs中,越靠前的节点的拓扑序越大。
AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=1e5+; int n,m;
int num;
int head[maxn];
struct Edge
{
int to;
int next;
}G[*maxn];
void addEdge(int u,int v)
{
G[num]={v,head[u]};
head[u]=num++;
}
struct SCC
{
int col[maxn];
bool vis[maxn];
vector<int >vs;
void DFS(int u)
{
vis[u]=true;
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if((i&) || vis[v])//正向边,num为偶数
continue;
DFS(v);
}
vs.push_back(u);
}
void RDFS(int u,int k)
{
vis[u]=true;
col[u]=k;
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if(!(i&) || vis[v])//反向边,num为奇数
continue;
RDFS(v,k);
}
}
int scc()
{
vs.clear();
mem(vis,false);
for(int i=;i <= n;++i)
if(!vis[i])
DFS(i); int k=;
mem(vis,false);
for(int i=vs.size()-;i >= ;--i)//从拓扑序的最大值开始查找SCC
if(!vis[vs[i]])
RDFS(vs[i],++k);
return k;
}
}_scc;
int Solve()
{
int k=_scc.scc();
int ans=;
int u;
for(int i=;i <= n;++i)
if(_scc.col[i] == k)
{
ans++;
u=i;
}
mem(_scc.vis,false);
_scc.RDFS(u,);//再次调用RDFS()判断u是否可以到达其他任意节点
for(int i=;i <= n;++i)
if(!_scc.vis[i])
return ;
return ans;
}
void Init()
{
num=;
mem(head,-);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
Init();
for(int i=;i <= m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
addEdge(u,v);
addEdge(v,u);
}
printf("%d\n",Solve());
}
return ;
}