当前位置:首页 > 高性能开发 > 数据结构与算法

poj 2186 强接通(经典题型)

优良自学吧提供poj 2186 强接通(经典题型),poj 2186 强连通(经典题型)题目链接  http://poj.org/problem?id=2186 Popular Cows Time Limit: 2000MS   Memory Limit: 65536K Total Submissi

poj 2186 强连通(经典题型)

题目链接  http://poj.org/problem?id=2186

Popular Cows
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 25044   Accepted: 10261

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. 
思路:
  判断给出的有向图中出度为0的联通分量的个数,如果为1就输出联通分量中的点的数目,否则输出0
  因为这个题是一个稀疏图,所以我们使用邻接表来存
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>

using namespace std;
const int maxn=10000+10;
struct node
{
    int v,next;
}e[maxn*5];
int T,index,n,m,top,cnt;
int head[maxn],in_s[maxn],dfn[maxn],low[maxn],belong[maxn],out[maxn],s[maxn];
void  build(int u,int v)
{
    e[T].v=v;
    e[T].next=head[u];
    head[u]=T++;
}
inline int Min(int &a,int &b)
{
    return a<b?a:b;
}
void init()
{
    memset(head,-1,sizeof(head));
    memset(in_s,0,sizeof(in_s));
    memset(dfn,-1,sizeof(dfn));
    memset(low,-1,sizeof(low));
    memset(belong,-1,sizeof(belong));
    memset(out,0,sizeof(out));
    T=0;
    index=0;
    cnt=1;
    top=0;
    int u,v;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u,&v);
        build(u,v);
    }
}
void dfs(int now)
{
    dfn[now]=low[now]=cnt++;
    s[++top]=now;
    in_s[now]=1;
    for(int i=head[now];~i;i=e[i].next)
    {
        int v=e[i].v;
        if(dfn[v]==-1)
        {
            dfs(v);
            low[now]=Min(low[now],low[v]);
        }
        else if(in_s[v])
        {
            low[now]=Min(low[now],dfn[v]);
        }
    }
    if(dfn[now]==low[now])
    {
        index++;
        int temp;
        do
        {
            temp=s[top--];
            belong[temp]=index;
            in_s[temp]=0;
        }while(temp!=now);
    }
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==-1)
        dfs(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];~j;j=e[j].next)
        {
            int v=e[j].v;
            if(belong[i]!=belong[v])
            {
                out[belong[i]]++;
            }
        }
    }
    int temp,num=0;
    for(int i=1;i<=index;i++)
    {
        if(!out[i])
        {
            num++;
            temp=i;
        }
    }
    int ans=0;
    if(num==1)
    {
        for(int i=1;i<=n;i++)
        {
            if(belong[i]==temp)
                ans++;
        }
        printf("%d\n",ans);
    }
    else
        printf("0\n");
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

 


(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢

最近更新