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)


相关推荐

  • 下拉刷新Demo[通俗易懂]

    下拉刷新Demo[通俗易懂]引用了网上的demo。packagecom.news.utils;importjava.text.SimpleDateFormat;importjava.util.Date;importcom.news.todaynews.R;importandroid.content.Context;importandroid.util.AttributeSet;impor

    2022年10月30日
  • intellij IDEA更换主题为Darcula后中文项目名称变口(方框)的解决办法

    intellij IDEA更换主题为Darcula后中文项目名称变口(方框)的解决办法刚开始试用IDEA,不大喜欢默认的intellij主题,于是在file—

  • 解析近期爆发的服务器挖矿病毒原理

    解析近期爆发的服务器挖矿病毒原理事情起因:同事解决服务器中挖矿病毒的过程可以看到,病毒的主要起因是利用了Linux预加载型恶意动态链接库的后门,关于Linux预加载的知识可以参考这一篇文章:警惕利用Linux预加载型恶意动态链接库的后门 一、准备工作我们导出病毒文件 libioset.so,然后利用IDA反编译该so文件,得到如下图的函数列表:可以看到,里面有许多我们熟悉的库函数,例如fope…

  • WebView中的视频全屏的相关操作

    WebView中的视频全屏的相关操作

    2021年11月30日
  • java时间类的使用和区别

    java时间类的使用和区别java中经常使用的6大时间类:java.util.Date              日期格式:年月日时分秒java.sql.Date               日期格式:年月日java.sql.Time               日期格式:时分秒java.sql.Timestamp          日期格式:年月日时分秒纳秒    从数据库中取出来的日期一般都用getTimestamp(…

  • Java标识符规范

    Java标识符规范?标识符标识符是我们给变量、类、方法等取的名字。取名规则:1.标识符中可以包含字母(中文)、下划线、美元符$、数字,不能包含其他符号2.标识符不能以数字开头3.标识符不能是关键字命名建议:1.类名,每个单词的首字母大写(大驼峰)例如:MyFirstApp,TestApp等2.方法名,首字母小写,后面每个单词开头大写例如:getHttpMessage(),localValue等3.变量名,和方法名规则一样。4.常量命名全部大写,每个单词间下划线分开5.字定义的标识符在命名时,使用尽

发表回复

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

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