首页 > 代码库 > Popular Cows

Popular Cows

2024-09-21 08:37:28   218人阅读

传送门（poj）：http://poj.org/problem?id=2186

          (bzoj):http://www.lydsy.com/JudgeOnline/problem.php?id=1051

 

Popular Cows
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 33482   Accepted: 13638

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
【解析】
呵呵哒。在poj上测怎么都是WA，半天错误都没找出来。数组我又开大点也没用。网友提供的十多组数据我都A啊。然后我就去bzoj上测的A了，100ms.
所以下面的代码poj上是过不了的。哼poj浪费我时间。上面两个传送门。
 
tarjan求强连通分量+缩点。
求出缩点后出度为0的点的个数，如果个数是1，输出这个连通块的牛的个数。否则不存在被所有牛都喜欢的牛。
 
我欢迎你，你欢迎他，我就欢迎他。
如果有S头牛互相喜欢，如果有一头牛喜欢S头牛中的任意一头，那么那头牛就喜欢这S头牛。
将互相喜欢的牛缩成一个点，如果某一个点的出度为0，那么所有的牛都喜欢它。注意是结果是连通块里牛的个数。
【代码】
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
#define N 10009
struct Edge
{
    int x,y,next;
    Edge(int x=0,int y=0,int next=0):
        x(x),y(y),next(next){}
}edge[N*5];
int sumedge,n,m,x,y,tim,top,sumclr,sumedge2,js,ans;
int head[N],dfn[N],low[N],Stack[N],color[N],cnt[N],out[N],head2[N];
bool vis[N],instack[N];
void ins(int x,int y)
{
    edge[++sumedge]=Edge(x,y,head[x]);
    head[x]=sumedge;
}
void ins2(int x,int y)
{
    edge[++sumedge2]=Edge(x,y,head2[x]);
    head2[x]=sumedge2;
}
map<int,bool>Map[N];
void tarjan(int x)
{
    dfn[x]=low[x]=++tim;
    vis[x]=1;instack[x]=1;Stack[++top]=x;
    for(int u=head[x];u;u=edge[u].next)
        if(instack[edge[u].y])
        low[x]=min(low[x],dfn[edge[u].y]);
        else
        if(!vis[edge[u].y])
        {
            tarjan(edge[u].y);
            low[x]=min(low[x],low[edge[u].y]);
        }
        else
        {
        }
        if(dfn[x]==low[x])
        {
            sumclr++;
            color[x]=sumclr;
            cnt[sumclr]++;
            while(Stack[top]!=x)
            {
                color[Stack[top]]=sumclr;//染色 
                instack[Stack[top]]=0;
                top--;
                cnt[sumclr]++;//记录这个连通块里牛的个数 
            }
            instack[x]=0;
            top--;
        }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        ins(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])tarjan(i);
        top=0;
    }
    for(int i=1;i<=n;i++)
        for(int u=head[i];u;u=edge[u].next)
            if(color[i]!=color[edge[u].y])
             if(Map[color[i]].find(color[edge[u].y])==Map[color[i]].end())    //缩点            
            {
                Map[color[i]][color[edge[u].y]]=true;
                ins2(color[i],color[edge[u].y]);
                out[color[i]]++;
            }
            int cnnt=0;
    for(int i=1;i<=sumclr;i++)
    {
        if(out[i]==0)//度为0意味着所有牛都欢迎他 
        {
            js++;
            ans=i;
            cnnt+=cnt[i];//加上这个连通块里牛的个数 
        }
    }
    if(js>1||js==0)puts("0");//如果有大于1个的度为0的点，说明这个图不是连通的。 
    else
    printf("%d",cnnt);
    return 0;
}

 

Popular Cows


联系
我们