POJ 2186 Popular Cows


强连通分量+缩点。一开始缩点之后用了平方的效率去处理,1200ms。。其实只要缩点之后把得到的图把每条边反向,每个节点统计一下入度,如果有多于一个点的入度大于0,答案肯定是0;否则答案就是那个入度为1的缩点里面牛的个数,360ms过了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
vector<int>G[maxn];
vector<int>FG[maxn];
int Flag[maxn];
int n,m,tot;
int dfn[maxn];
int u[5*maxn],v[5*maxn];
struct Node
{
    int id,val;
} node[maxn];

//缩点
int Tot[maxn];//一个点有几个人
int JiHe[maxn];//属于哪个点
int FF[maxn];
int BianHao;
int RuDu[maxn];
vector<int>New[maxn];


void init()
{
    for(int i=0; i<=n; i++) G[i].clear();
    for(int i=0; i<=n; i++) FG[i].clear();
    for(int i=0; i<=n; i++) New[i].clear();
    memset(dfn,0,sizeof(dfn));
    memset(Flag,0,sizeof(Flag));
    memset(Tot,0,sizeof(Tot));
    memset(JiHe,-1,sizeof(JiHe));
    memset(RuDu,0,sizeof(RuDu));
    BianHao=1;
    tot=1;
}
void Dfs(int now)
{
    dfn[now]=tot;
    tot++;
    for(int i=0; i<G[now].size(); i++)
        if(!dfn[G[now][i]])
            Dfs(G[now][i]);
}
bool cmp(const Node&a,const Node&b)
{
    return a.val<b.val;
}

void DFS(int now)
{
    Flag[now]=1;
    // printf("%d ",now);
    JiHe[now]=BianHao;
    Tot[BianHao]++;
    for(int i=0; i<FG[now].size(); i++)
        if(!Flag[FG[now][i]])
            DFS(FG[now][i]);
}

void DDfs(int now)
{
    FF[now]=1;
    for(int i=0; i<New[now].size(); i++)
        DDfs(New[now][i]);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&u[i],&v[i]);
            G[u[i]].push_back(v[i]);
            FG[v[i]].push_back(u[i]);
        }
        Dfs(1);
        for(int i=0; i<n; i++)
        {
            node[i].id=i+1;
            node[i].val=dfn[i+1];
        }
        sort(node,node+n,cmp);
        for(int i=0; i<n; i++)
            if(!Flag[node[i].id])
            {
                DFS(node[i].id);
                BianHao++;
            }
        for(int i=0; i<m; i++)
            if(JiHe[u[i]]!=JiHe[v[i]])
                RuDu[JiHe[u[i]]]++;
        int k;
        int ans=0;
        int Zong=0;
        for(int i=1; i<BianHao; i++)
        {
            if(!RuDu[i])
            {
                Zong++;
                ans=Tot[i];
            }
        }
        if(Zong==1) printf("%d\n",ans);
        else printf("0\n");
    }
    return 0;
}

优质内容筛选与推荐>>
1、url重写实现任意二级域名或多级域名
2、Linq一些简单的用法
3、边沿检测方法-FPGA入门教程
4、面试常见问题-SQL
5、Web实时通信之Socket.IO


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号