Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.
* Line 1: A single integer that is the number of cows who are considered popular by every other cow.
#include
#include
#include
using namespace std;
const int maxn=100000;
struct edge
{
int t,w;//u->t=w;
int next;
};
int V,E;//点数(从1开始)，边数
int p[maxn],pf[maxn];//邻接表原图,逆图
edge G[maxn],Gf[maxn];//邻接表原图,逆图
int l,lf;
void init()
{
memset(p,-1,sizeof(p));
memset(pf,-1,sizeof(pf));
l=lf=0;
}
void addedge(int u,int t,int w,int l)
{
G[l].w=w;
G[l].t=t;
G[l].next=p[u];
p[u]=l;
}
void addedgef(int u,int t,int w,int l)
{
Gf[l].w=w;
Gf[l].t=t;
Gf[l].next=pf[u];
pf[u]=l;
}
///Kosaraju算法,返回为强连通分量个数
bool flag[maxn]; //访问标志数组
int belg[maxn]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量
int numb[maxn]; //结束时间(出栈顺序)标记,其中numb[i]表示离开时间为i的顶点
//用于第一次深搜,求得numb[1..n]的值
void VisitOne(int cur, int &sig)
{
flag[cur] = true;
for (int i=p[cur];i!=-1;i=G[i].next)
{
if (!flag[G[i].t])
{
VisitOne(G[i].t,sig);
}
}
numb[++sig] = cur;
}
//用于第二次深搜,求得belg[1..n]的值
void VisitTwo(int cur, int sig)
{
flag[cur] = true;
belg[cur] = sig;
for (int i=pf[cur];i!=-1;i=Gf[i].next)
{
if (!flag[Gf[i].t])
{
VisitTwo(Gf[i].t,sig);
}
}
}
//Kosaraju算法,返回为强连通分量个数
int Kosaraju_StronglyConnectedComponent()
{
int i, sig;
//第一次深搜
memset(flag,0,sizeof(flag));
for ( sig=0,i=1; i<=V; ++i )
{
if ( false==flag[i] )
{
VisitOne(i,sig);
}
}
//第二次深搜
memset(flag,0,sizeof(flag));
for ( sig=0,i=V; i>0; --i )
{
if ( false==flag[numb[i]] )
{
VisitTwo(numb[i],++sig);
}
}
return sig;
}
//缩点
int n;//缩点后的点个数1~n
int g[maxn];
edge eg[maxn];//邻接表
int re;
int cont[maxn];
int cnt0,index;//出度为0的点
void dinit(int sig)
{
memset(g,-1,sizeof(g));
n=sig;
re=cnt0=0;
memset(cont,0,sizeof(cont));//1~n 第sig块强联通分量中的点数
}
void addedge0(int u,int t,int w,int l)
{
eg[l].w=w;
eg[l].t=t;
eg[l].next=g[u];
g[u]=l;
}
int main()
{
while(scanf("%d%d",&V,&E)==2)
{
init();
for(int i=0;i
{
int u,t,w=1;scanf("%d%d",&u,&t);
addedge(u,t,w,l++);
addedgef(t,u,w,lf++);
}
int ans=Kosaraju_StronglyConnectedComponent();
//printf("%d/n",ans);
///缩点
dinit(ans);
for(int i=1;i<=V;i++)//构图
{
for(int j=p[i];j!=-1;j=G[j].next)
{
int st=belg[i],ed=belg[G[j].t];
if(st!=ed)
{
addedge0(st,ed,1,re++);
}
}
}
//计算每块强联通分量中的点个数
for(int i=1;i<=V;i++)
{
cont[belg[i]]++;
}
//计算图中出度为0的点
for(int i=1;i<=n;i++)
{
if(g[i]==-1)
{
cnt0++;
index=i;
}
}
/*有向无环图中唯一出度为0的点，一定可以由任何点出发均可达
有向无环图中所有入度不为0的点，一定可以由某个入度为0的点出发可达
*/
if(cnt0==1) printf("%d/n",cont[index]);
else printf("0/n");
}
return 0;
}
京公网安备 11010802041100号