POJ2186 Popular Cows 【强连通分量】+【Kosaraju】+【Tarjan】+【Garbow】

POJ2186 Popular Cows 【强连通分量】+【Kosaraju】+【Tarjan】+【Garbow】

大家好,又见面了,我是全栈君。

Popular Cows
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 23445   Accepted: 9605

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

题意:能够转换成“给定一些有向路,求有多少个点能够由其余的随意点到达。

题解:第一道强连通分量的题,大致总结下Kosaraju算法:求强连通分量主要是为了简化图的构造,假设分量外的一个点能到达分量内的当中一个点,那么它必然能到达分量内的全部点,所以某种程度上。强连通分量能够简化成一个点。详细的求解过程是:1、随意选定一个点開始对原图进行深搜,记录每一个点离开时的时间(更确切的说是求每一个时间相应哪个点离开)。2、对原图的反图进行深搜,步骤一中最后离开的点最先開始深搜。每次将同一棵树中的点都哈希成同一个值。最后有多少棵树就有多少个强连通分量。

这题最后全部点都哈希完毕后实际上构成了一个DAG。假设新图中出度为0的点仅仅有一个那么有解,解为该出度为0的强连通分量中原来点的个数。若出度为0的点不止一个,那么无解,由于有两群牛互不崇拜,此时答案为0.在推断连通分量是否有出度时有个小技巧,就是在对反图DFS时若发现连接到的点已訪问且它的哈希值与当前訪问点的哈希值不同。那么这个被连接到的点相应的联通分量是有出度的。然后还需记录每一个连通分量的点数。

#include <stdio.h>
#include <string.h>
#define maxn 10002
#define maxm 50002

int head0[maxn], head1[maxn], id;
int count[maxn], num[maxn], hash[maxn];
struct Node{
    int t0, next0, t1, next1;
} E[maxm];
bool vis[maxn], out[maxn];

void addEdge(int u, int v)
{
    E[id].t0 = v; E[id].next0 = head0[u];
    head0[u] = id; E[id].t1 = u;
    E[id].next1 = head1[v]; head1[v] = id++;
}

void getMap(int n, int m)
{
    int i, u, v; id = 0;
    memset(head0, -1, sizeof(int) * (n + 1)); //save time
    memset(head1, -1, sizeof(int) * (n + 1));
    for(i = 0; i < m; ++i){
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }
}

void DFS0(int pos, int& sig)
{
    vis[pos] = 1; int i;
    for(i = head0[pos]; i != -1; i = E[i].next0){
        if(!vis[E[i].t0]) DFS0(E[i].t0, sig);
    }
    num[++sig] = pos;
}

void DFS1(int pos, int sig)
{
    vis[pos] = 1; hash[pos] = sig;
    int i; ++count[sig];
    for(i = head1[pos]; i != -1; i = E[i].next1){
        if(!vis[E[i].t1]) DFS1(E[i].t1, sig);
        else if(hash[E[i].t1] != hash[pos]) out[hash[E[i].t1]] = 1;
    }
}

void solve(int n) //Kosaraju
{
    int i, sig = 0, tmp = 0, ans;
    memset(vis, 0, sizeof(bool) * (n + 1));
    for(i = 1; i <= n; ++i)
        if(!vis[i]) DFS0(i, sig);
    memset(vis, 0, sizeof(bool) * (n + 1));
    memset(count, 0, sizeof(int) * (n + 1));
    memset(out, 0, sizeof(bool) * (n + 1));
    i = sig; sig = 0;
    for(; i; --i)
        if(!vis[num[i]]) DFS1(num[i], ++sig);
    for(i = 1; i <= sig; ++i)
        if(!out[i]) ++tmp, ans = count[i];
    //printf("sig%d\n", sig);
    if(tmp == 1) printf("%d\n", ans);
    else printf("0\n");
}

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) == 2){
        getMap(n, m);
        solve(n);
    }
    return 0;
}

Tarjan解法:

#include <stdio.h>
#include <string.h>
#define maxn 10002
#define maxm 50002

int head[maxn], vis[maxn], id, id2, scc_num, sec;
int dfn[maxn], low[maxn], sta[maxn], count[maxn];
bool out[maxn];
struct Node{
    int to, next;
} E[maxm];

int min(int a, int b){
    return a < b ?

a : b;}void addEdge(int u, int v){ E[id].to = v; E[id].next = head[u]; head[u] = id++;}void getMap(int n, int m){ int i, u, v; id = 0; memset(head, -1, sizeof(int) * (n + 1)); memset(vis, 0, sizeof(int) * (n + 1)); memset(out, 0, sizeof(bool) * (n + 1)); memset(count, 0, sizeof(int) * (n + 1)); for(i = 0; i < m; ++i){ scanf("%d%d", &u, &v); addEdge(u, v); }}void DFS(int pos) //强连通分量必然是该树的子树{ dfn[pos] = low[pos] = ++sec; vis[pos] = 1; sta[id2++] = pos; int i, u, v; for(i = head[pos]; i != -1; i = E[i].next){ v = E[i].to; if(!vis[v]) DFS(v); if(vis[v] == 1) low[pos] = min(low[pos], low[v]); } if(dfn[pos] == low[pos]){ ++scc_num; do{ ++count[scc_num]; u = sta[--id2]; low[u] = scc_num; vis[u] = 2; } while(u != pos); }}void solve(int n) //Tarjan{ int i, j, ok = 0, ans; sec = id2 = scc_num = 0; for(i = 1; i <= n; ++i) if(!vis[i]) DFS(i); for(i = 1; i <= n; ++i) for(j = head[i]; j != -1; j = E[j].next) if(low[i] != low[E[j].to]){ out[low[i]] = 1; break; } for(i = 1; i <= scc_num; ++i) if(!out[i]){ if(++ok > 1) break; ans = count[i]; } if(ok != 1) printf("0\n"); else printf("%d\n", ans);}int main(){ int n, m; while(scanf("%d%d", &n, &m) == 2){ getMap(n, m); solve(n); } return 0;}

Garbow解法:与Tarjan思想同样,仅仅是实现方式略有不同,效率更高一些。

#include <stdio.h>
#include <string.h>
#define maxn 10002
#define maxm 50002
//sta2用以维护当前连通分量的根
int head[maxn], id, sta1[maxn], id1, sta2[maxn], id2;
int low[maxn], scc[maxn], sccNum, sec, count[maxn];
struct Node{
    int to, next;
} E[maxm];
bool out[maxn];

void addEdge(int u, int v)
{
    E[id].to = v; 
    E[id].next = head[u];
    head[u] = id++;
}

void getMap(int n, int m)
{
    int i, u, v; id = 0;
    memset(head, -1, sizeof(int) * (n + 1));
    for(i = 0; i < m; ++i){
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }
}

void Garbow(int pos)
{
    low[pos] = ++sec;
    sta1[id1++] = sta2[id2++] = pos;
    for(int i = head[pos]; i != -1; i = E[i].next){
        if(!low[E[i].to]) Garbow(E[i].to);
        else if(!scc[E[i].to]){
            while(low[sta2[id2-1]] > low[E[i].to]) --id2;
        }
    }
    if(pos == sta2[id2-1]){        
        int v; ++sccNum; --id2;
        do{
            v = sta1[--id1];
            scc[v] = sccNum;
            ++count[sccNum];
        } while(sta1[id1] != pos);
    }
}

void solve(int n)
{
    int i, j; id1 = id2 = sec = sccNum = 0;
    memset(low, 0, sizeof(int) * (n + 1));
    memset(scc, 0, sizeof(int) * (n + 1));
    memset(count, 0, sizeof(int) * (n + 1));
    memset(out, 0, sizeof(bool) * (n + 1));
    for(i = 1; i <= n; ++i)
        if(!low[i]) Garbow(i);
    for(i = 1; i <= n; ++i)
        for(j = head[i]; j != -1; j = E[j].next)
            if(scc[i] != scc[E[j].to]){
                out[scc[i]] = 1; break;
            }
    int tmp = 0, ans;
    for(i = 1; i <= sccNum; ++i)
        if(!out[i]){
            if(++tmp > 1){
                ans = 0; break;
            }
            ans = count[i];
        }
    printf("%d\n", ans);
}

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) == 2){
        getMap(n, m);
        solve(n);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115896.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • spark中flatMap函数用法–spark学习(基础)「建议收藏」

    spark中flatMap函数用法–spark学习(基础)「建议收藏」说明在spark中map函数和flatMap函数是两个比较常用的函数。其中map:对集合中每个元素进行操作。flatMap:对集合中每个元素进行操作然后再扁平化。理解扁平化可以举个简单例子valarr=sc.parallelize(Array((“A”,1),(“B”,2),(“C”,3)))arr.flatmap(x=>(x._1+x._2)).foreach(println)输出

  • python光流法算法学习「建议收藏」

    python光流法算法学习「建议收藏」基于python-opencv程序对光流法的理解光流法的定义Lucas-Kanade光流原理Shi-Tomasi角点检测python-opencv代码demo光流法的定义光流法是空间运动物体在观察成像平面上的像素运动的瞬时速度,是利用图像序列中像素在时间域上的变化以及相邻帧之间的相关性来找到上一帧跟当前帧之间存在的对应关系,从而计算出相邻帧之间物体的运动信息的一种方法。一般而言,光流是由于场景…

  • java英文文献和翻译_javaweb参考文献

    java英文文献和翻译_javaweb参考文献外文文献及翻译:JavaandtheInternet1JavaandtheInternetIfJavais,infact,yetanothercomputerprogramminglanguage,youmayquestionwhyitissoimportantandwhyitisbeingpromotedasarevolutionary…

  • GOland2021 激活码破解方法

    GOland2021 激活码破解方法,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 预写式日志(Write-Ahead Logging (WAL))

    预写式日志(Write-Ahead Logging (WAL))

    2021年11月25日
  • statement和prepareStatement 的区别

    statement和prepareStatement 的区别????Java基础教程系列:Java基础教程系列????Java学习路线总结:搬砖工逆袭Java架构师????Java经典面试题大全:10万字208道Java经典面试题总结(附答案)????简介:Java领域优质创作者????、CSDN哪吒公众号作者✌、Java架构师奋斗者????????扫描主页左侧二维码,加入群聊,一起学习、一起进步????欢迎点赞????收藏⭐留言????一、【粉丝福利】送书啦,大家期待已久的Vue!本次活动送书规则:【送

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号