poj2186 最受欢迎的牛(求最受欢迎的牛的数量)

Popular Cows

Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 27531   Accepted: 11077

Description

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.

Input

* Line 1: Two space-separated integers, N and M

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.

Output

* Line 1: A single integer that is the number of cows who are considered popular by every other cow.

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

Hint

Cow 3 is the only cow of high popularity.

Source

USACO 2003 Fall

本题题意时每个牛都可以仰慕求它的牛,而且仰慕关系可以互相传递

问最受欢迎的牛的数量有多少个

可以利用强联通的缩点法,最后求缩点之后的初度为0的点的数量,

注意一个问题就是:

如果没有出度为0的点,那么结果输出答案为0

下面提供了几组样例,主要注意的输出为0的点需要特别判断

解决该题目的模板同上面的那个解决学校之间传递数量文件关系的拿到题所用的模板都是一套模板,而且判断入度出度那里也咩有变化

ps::附上嗲吗

#include <string.h>
#include <stdio.h>
#define V    10500
#define E    50500

struct edge
{
    int to, next;
}Edge[E];
int head[V], e, n;

int indeg[V], outdeg[V]; //点的入度和出度数
int belong[V], low[V], dfn[V], scc, cnt;//dfn[]:遍历到u点的时间; low[]:u点可到达的各点中最小的dfn[v]
int S[V], top;
bool vis[V];//v是否在栈中

int addedge(int u, int v)
{
    Edge[e].to = v;
    Edge[e].next = head[u];
    head[u] = e++;
    return 0;
}
void tarjan(int u)
{
    int v;
    dfn[u] = low[u] = ++cnt;//开始时dfn[u] == low[u]
    S[top++] = u;//不管三七二十一进栈
    vis[u] = true;
    for (int i=head[u]; i!=-1; i=Edge[i].next)
    {
        v = Edge[i].to;
        if (dfn[v] == 0)//如果v点还未遍历
        {
            tarjan(v);//向下遍历
            low[u] = low[u] < low[v] ? low[u] : low[v];//确保low[u]最小
        }
        else if (vis[v] && low[u] > dfn[v])//v在栈中,修改low[u]
            low[u] = dfn[v];
    }
    if (dfn[u] == low[u])//u为该强连通分量中遍历所成树的根
    {
        ++scc;
        do
        {
            v = S[--top];//栈中所有到u的点都属于该强连通分量,退栈
            vis[v] = false;
            belong[v] = scc;
        } while (u != v);
    }

}

int solve(){
    scc = top = cnt = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(vis, false, sizeof(vis));
    for (int u=1; u<=n; ++u)
        if (dfn[u] == 0)
            tarjan(u);
    return scc;
}

void count_deg()
{
    memset(indeg, 0, sizeof(indeg));
    memset(outdeg, 0, sizeof(outdeg));
    for (int u=1; u<=n; ++u)
        for (int i=head[u]; i!=-1; i=Edge[i].next)
        {
            int v = Edge[i].to;
            if (belong[u] != belong[v])
            {
                indeg[belong[v]]++;
                outdeg[belong[u]]++;
            }
        }
}

int main()
{
    int u, v, i;
    int m;
    while (~scanf("%d%d", &n,&m))
    {
        e = 0;
        memset(head, -1, sizeof(head));
        for (int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
                addedge(u, v);
        }
        solve();
            count_deg();

          int num=0,tmp;
        for(int i = 1; i <= scc; i++)
        {
            if(!outdeg[i])
            {
                num++;
                tmp = i;
            }  

        }
          int ans=0;
        if(num == 1)
        {
            for(int i = 1; i <= n; i++)
            {
                if(belong[i] == tmp)
                    ans++;
            }
            printf("%d\n", ans);
        }
        else
        {
            printf("0\n");
        }  

    }
    return 0;
}
时间: 09-04

poj2186 最受欢迎的牛(求最受欢迎的牛的数量)的相关文章

你不牛逼,认识再多牛逼的人,也与你无关(转)

寂静的夜,人们总是习惯在这个时候,去独自思考人生.回想过往的辉煌与落寞.至少我是这样,在我工作近十年的时间里,这个“恶习”一直陪伴着我.在深夜,我会复盘曾经失去的钱权与感情,尝试着找寻其中的规律,让自己在下一次尽量避免.事实也的确如此,同样的错误我很少在遇到.当然,有种错误叫做“原则”,这个我是没有办法避免的. 有人曾经问我这样会不会很累,其实我也不知道.虽然我每天只休息 4 个小时不到,但是却依然可以精神充沛,也许是我爱我的职业.至于问我这个问题的朋友,现在已经返乡,走的时候,还在向我抱怨北京

weblogic 12c 一键静默建域、集群、受管,计算机以及添加受管到集群

1.静默安装(参照以往文章) 2.静默建域.集群.受管,计算机以及添加受管到集群 编写响应文件,内容包括主管端口,ssl端口,集群名字,受管名字,计算机名字,以及受管添加到哪个集群并且设置主管密码 [[email protected] ~]$ cat creat.rsp read template from "/home/weblogic/Oracle/Middleware/Oracle_Home/wlserver/common/templates/wls/wls.jar"; set

《编程题》穷举法求N年后有多少头牛

若一头小母牛,从出生起第四个年头开始每年生一头母牛,按这个规律,第N年时有多少头母牛? 1 #include <iostream> 2 3 int main(int argc, const char * argv[]) { 4 5 int N = 0; 6 7 std::cout<<"请输入年份\n"; 8 std::cin>>N; 9 int *iA; 10 11 if((iA = (int *)malloc(N*sizeof(int)))==NU

用七牛sdk传递图片到七牛服务器

第一步申请七牛的开发者账号,申请完了之后,可以获取accesskey和secrect key 参照官方网站的java的demo 下载了依赖的jar包,放到/Library/Java/Extentiosns目录下 将对应的accesskey  secretkey填入 即可上传图片 import com.qiniu.util.Auth; import java.io.IOException; import com.qiniu.common.QiniuException; import com.qin

使用python实现将截图上传到七牛服务器,并将七牛生成的外部链接添加的剪切板的功能

目的:在使用markdown来记录文档时,不必每次都将截图存到文档中,只需将图片链接存放到文档中,此时就想到了需要使用云服务器和自动上传文件的功能 OS: Ubuntu 15.10 version 0.1: 工具:截图工具shutter, 剪切板操作工具: xsel 源代码: 1 #!/usr/bin/python 2 import time ##时间模块,使用时间戳生成唯一的文件名 3 import commands ##python中的执行shell命令的模块 4 import os ##同

JSF页面中的JS取得受管bean的数据(受管bean发送数据到页面)

JSF中引入jsf.js文件之后,可以拦截jsf.ajax.request请求.一直希望有一种方法可以像jquery的ajax一样,能在js中异步取得服务器端发送的数据.无奈标准JSF并没有提供这样的方法.在一些JSF框架里面提供了这样的方法,比如primefaces的onComplete方法就是返回数据到一个js方法中的.JSF能在bean里面更新视图(非ajax更新),其中的PartialViewContext类就可以做到局部更新UI,在bean里获取到这个UI就可以了.于是在网上翻看了很多

【警语】受得小气,则不至于受大气;吃得小亏,则不至于吃大亏

能够忍受小的欺凌,就不至于招惹更大的灾祸侮辱:面对一切微小的不公平待遇,或者利益分配有所冲突时,能够退让,不和人争蝇头小利,才不至于遭受更多损失. 我们在现实中很容易看到,无论是人与人之间.团体之间,甚至国家.种族之间,往往只是一句话的不和.一件极小的事情不能忍受,酿成许多惨剧,招来杀身之祸.牢狱之灾.财物重大损失.国家的动荡不安.教训惨痛,当事人往往后悔莫及. 面对别人的横加欺侮.障碍打击,乃至一切貌似不公正的处境,我们能够逆来顺受,不予计较,才能化解纠纷,消灾免难.这需要肚量,更需要智慧.首

【BZOJ1051】1051: [HAOI2006]受欢迎的牛 tarjan求强连通分量+缩点

Description 每一头牛的愿望就是变成一头最受欢迎的牛.现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎. 这种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎.你的任务是求出有多少头牛被所有的牛认为是受欢迎的. Input 第一行两个数N,M. 接下来M行,每行两个数A,B,意思是A认为B是受欢迎的(给出的信息有可能重复,即有可能出现多个A,B) Output 一个数,即有多少头牛被所有的牛认为是受欢迎的. Sample Input 3 3

不裸缩点》。。。POJ2186受欢迎的牛

html,body { font-size: 15px } body { font-family: Helvetica, "Hiragino Sans GB", "微软雅黑", "Microsoft YaHei UI", SimSun, SimHei, arial, sans-serif; line-height: 1.6; margin: 0; padding: 1.33rem 1rem } h1,h2,h3,h4,h5,h6 { margin