总算把USACO的受欢迎奶牛做出来了

题目描述:

有一些奶牛,其中某些奶牛受其他奶牛欢迎。每头奶牛都喜欢自己,同时都追随它喜欢奶牛的爱好。如果A喜欢B,而B喜欢C,那么A也会喜欢C。如果所有人都喜欢某头奶牛,那么这头奶牛就称之为绝对奶牛。

现在有N头奶牛,同时告诉你M条A喜欢B的信息,请你计算出有多少头绝对奶牛。

输入描述:

输入文件第一行是N和M。此后M行,每行两个整数A,B(1<=A,B<=N),表示奶牛B受奶牛A欢迎,也就是奶牛A喜欢奶牛B。

输出描述:

输出文件仅有一行,是绝对奶牛的数目。

输入样例:

3 3
1 2
2 1
2 3

输出样例:

1

数据范围:

对于30%的数据,有1<=N<=1000,1<=M<=5000;

对于100%的数据,有1<=N<=100000,1<=M<=500000。

-----------------------------------------------------------------

这道题我初次想要用拓扑排序做,发现会超时

然后改成Tarjan... 请自行搜索Tarjan求强连通分支

后来发现大数据会RE

用-Wl,--stack=134217728(设定栈大小为128M)就好了

所以是暴递归栈了

Egg Pain的我就Egg Pain地写了一个Egg Pain的递归栈模拟,纪念如下

不是很清晰,自行理解后再手打吧,抄袭不好。!

天呢,花了我一周调试~默一遍有助理解

#include <cstdio>
#include <algorithm>
struct Edge {
    int from, to;
    Edge* next;
};
const int MAXN = 100001, MAXM = 500001;
struct UFS {
    int father[MAXN], rank[MAXN], root(int);
    void initialize(int), plus(int, int);
    ~UFS();
};
struct Cell {
    int x;
    bool finished, first, visjto;
    Edge* j;
    void call();
};
int n, m, low[MAXN], dfn[MAXN], nowdfn, stk[MAXN], top, s[MAXN], cst;
bool vis[MAXN], ins[MAXN];
Edge* head[MAXN];
UFS ufs;
Cell cs[MAXN];
int main() {
    int cnt = 0, tmp;
    freopen("popular.in", "r", stdin);
    freopen("popular.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int s, t;
        Edge* tmp = new Edge;
        scanf("%d%d", &s, &t);
        tmp->from = s;
        tmp->to = t;
        tmp->next = head[s];
        head[s] = tmp;
    }
    ufs.initialize(n);
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            cst = 1;
            cs[cst].x = i;
            cs[cst].first = true;
            cs[cst].finished = false;
            while(cst != 0) {
                cs[cst].call();
                if(cs[cst].finished) {
                    cst--;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(Edge* j = head[i]; j != NULL; j = j->next) {
            if(ufs.root(i) != ufs.root(j->to)) {
                s[ufs.root(i)]++;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(ufs.root(i) == i && s[i] == 0) {
            cnt++;
            tmp = i;
        }
    }
    printf("%d\n", cnt == 1 ? ufs.rank[tmp] : 0);
    for(int i = 1; i <= n; i++) {
        while(head[i] != NULL) {
            Edge* tmp = head[i]->next;
            delete head[i];
            head[i] = tmp;
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void UFS::initialize(int n) {
    for(int i = 1; i <= n; i++) {
        father[i] = i;
        rank[i] = 1;
    }
}
int UFS::root(int x) {
    return father[x] == x ? x : root(father[x]);
}
void UFS::plus(int x, int y) {
    father[y] = x;
    rank[x] += rank[y];
}
UFS::~UFS() {
    delete[] father;
    delete[] rank;
}
void Cell::call() {
    if(first) {
        nowdfn++;
        top++;
        dfn[x] = low[x] = nowdfn;
        ins[x] = vis[x] = true;
        stk[top] = x;
        j = head[x];
        first = false;
    }
    else {
        if(!visjto) {
            low[x] = std::min(low[x], low[j->to]);
        }
        if(ins[j->to]) {
            low[x] = std::min(low[x], dfn[j->to]);
        }
        j = j->next;
    }
    if(j == NULL) {
        if(low[x] == dfn[x]) {
            int f = stk[top];
            top--;
            if(f != x) {
                while(true) {
                    int i = stk[top];
                    top--;
                    ufs.plus(f, i);
                    if(i == x) {
                        break;
                    }
                }
            }
        }
        finished = true;
    }
    else {
        if(!vis[j->to]) {
            cst++;
            cs[cst].x = j->to;
            cs[cst].first = true;
            cs[cst].finished = false;
            visjto = false;
        }
        else {
            visjto = true;
        }
    }
}
时间: 01-19

总算把USACO的受欢迎奶牛做出来了的相关文章

【COGS &amp; USACO】896. 圈奶牛(凸包)

http://cojs.tk/cogs/problem/problem.php?pid=896 我的计算几何入门题... 看了看白书的计算几何部分,,恩好嘛.. 乃们都用向量!!!! 干嘛非要将2个点确定一条线变成一个点从原点o出发的射线!!!! 这就是所谓的玩概念吗 然后用所谓的向量加减,是这些向量起点相同,然后就变成了原点o出发的射线!!! 然后你们还在玩概念!我跪了. (以上纯属蒟蒻吐槽) 好吧,计算几何非常有用的..简化了不少操作. 这里还有啥点积啥叉积.点积就是同一起点的向量(终点)的

7、8月刷题总结

准备开学了囧,7.8月刷题记录,以后好来复习,并且还要好好总结! 数据结构: splay: [BZOJ]1503: [NOI2004]郁闷的出纳员(Splay) [BZOJ]1269: [AHOI2006]文本编辑器editor(Splay) [BZOJ]1507: [NOI2003]Editor(Splay) treap: [BZOJ]1862: [Zjoi2006]GameZ游戏排名系统 & 1056: [HAOI2008]排名系统(treap+非常小心) [BZOJ]3224: Tyvj

oracle之sql查询二

此文章为http://huangsir007.blog.51cto.com/6159353/1854818该片的后续 关于数据库语言查询: SQL> show parameter nls_language; NAME                                 TYPE        VALUE ------------------------------------ ----------- ------------------------------ nls_languag

TYVJ P1029 牛棚回声 Label:坑

背景 USACO OCT09 3RD 描述 奶牛们灰常享受在牛栏中牟叫,因為她们可以听到她们牟声的回音.虽然有时候并不能完全听到完整的回音.Bessie曾经是一个出色的秘书,所以她精确地纪录了所有的牟叫声及其回声.她很好奇到底两个声音的重复部份有多长. 输入两个字符串(长度為1到80个字母),表示两个牟叫声.你要确定最长的重复部份的长度.两个字符串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串. 我们通过一个例子来理解题目.考虑下面的两个牟声: moyooyoxyzooo  

性能测试 - 响应 vs 延迟 vs 吞吐量 vs 负载 vs 扩展性 vs 压力 vs 健壮性

本文译自Niraj Bhatt 所著 Performance Testing - Response vs. Latency vs. Throughput vs. Load vs. Scalability vs. Stress vs. Stress vs. Robustness. 原文地址:https://nirajrules.wordpress.com/2009/09/17/measuring-performance-response-vs-latency-vs-throughput-vs-lo

豪情-2015年5月份书籍分享

豪情-2015年5月份书籍分享 blog 一. 前言 二. 职场相关 三. 前端相关 四. 其它 一. 前言 最近的新书,或以前的书分享一下.对一本书的好坏评价很难公平,公正.我只分享我感觉还可以,不要求达到每个人的认同或赞赏.每个人的知识基础,教育背景不一样,求存共异吧.另外补充自己不擅长的,有兴趣看看,勿喷,但可以在评论中推荐好书. 然后另外一个分享,到一定的阶段,技术书籍肯定不是占重要的比例了.找个时间或集中突击一下就ok,反而推荐管理方面或社会科学方面的一些书籍,是真正打开管理或社会万象

学习总结(一)

对于编程菜鸟级人物来说,很有必要先把最基础的知识学到!今天从jiang老师那里学到了很多,让我这个水货真正认识到自己的不足.没关系,缺什么补什么...只要愿意学,没有什么的:只要动手编,没有什么的.纠正好自己的心态! 下面都是关于编程的一些基础名词科普,让你清楚知道具体都有些什么功能.不能再是那种模棱两可,一定要清楚!不然后面的学习会很困难!以下的总结也有很多不全面的,希望大家纠正,共同学习,共同进步! 1 编辑器 编译器通常接受由任何生成标准文件(例如ASCII文件)的编辑器编写的源程序.现在

洛谷 P2879 [USACO07JAN]区间统计Tallest Cow 题解

此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置. 题目链接:https://www.luogu.org/problem/show?pid=2879 题目描述 FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told on

NodeJs支付宝移动支付签名及验签

非常感谢 :http://www.jianshu.com/p/8513e995ff3a?utm_campaign=hugo&utm_medium=reader_share&utm_content=note&utm_source=weibo 的文章,如果不是找到这篇文章我可能还要继续坑几天,代码也基本都是照着他的搬过来的,不过支付宝移动支付文档写的非常糟糕而且没有node的SDK和demo,写起来异常痛苦..好在找到了这篇文章顺便折腾了一下午支付宝的技术人员总算把移动支付整个流程给做