Tarjan缩点(把强连通分量看成一个点)�

// poj 2186 http://poj.org/problem?id=2186

// 翻译后的题意:每个母牛的梦想是成为牛群中最受欢迎的母牛。在N(1 <= N <= 10,000)头牛群中,您最多可以得到M(1 <= M <= 50,000)个有序对(A,B),它们告诉您A牛认为B很受欢迎。由于流行是传递性的,因此如果A认为B流行而B认为C流行,那么A也将认为C 
流行,即使未在输入中由有序对明确指定它也是如此。您的任务是计算被其他所有奶牛所欢迎的奶牛数量。
//将强联通分量缩点,找出出度为0的点,如果只有一个出度为0的点,那么这个点(也可能是经过缩点的点),包含的点的个数就是answer。如果出度为0的点 多于1个,这些出度为0的点之间就没有崇拜关系,肯定输出0了
//上句话从https://blog.csdn.net/u011026968/article/details/10283071复制而来。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 10000+5;
const int MAXM = 50000+5;

struct node {
    int v, next;
} edge[MAXM];
int num;

int head[MAXN];

inline void add_edge(int x, int y) {
    edge[num].v = y;
    edge[num].next = head[x];
    head[x] = num++;
}

int cnt, t, scc_cnt;
int dfn[MAXN], low[MAXN], sccno[MAXN], stack[MAXN];
int scc_num[MAXN], out[MAXN];

inline void Tarjan(int cur) {
    dfn[cur] = low[cur] = ++cnt;
    stack[t++] = cur;
    for(int i = head[cur]; i != -1; i = edge[i].next) {
        if(!dfn[edge[i].v]) {
            Tarjan(edge[i].v);
            low[cur] = min(low[cur], low[edge[i].v]);
        }
        else if(!sccno[edge[i].v]) {
            low[cur] = min(low[cur], dfn[edge[i].v]);
        }
    }
    if(dfn[cur] == low[cur]) {
        ++scc_cnt;
        int v;
        do {
            v = stack[--t];
            sccno[v] = scc_cnt;
            ++scc_num[scc_cnt];
        } while(v != cur);
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof(head));
    int x, y;
    for(int i = 0; i != m; ++i) {
        scanf("%d%d", &x, &y);
        add_edge(x, y);
    }
    for(int i = 1; i <= n; ++i) {
        if(!dfn[i]) Tarjan(i);
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = head[i]; j != -1; j = edge[j].next) {
            int a = sccno[i], b = sccno[edge[j].v];
            if(a != b) ++out[sccno[i]];
        }
    }
    int ans = 0;
    int flag;
    for(int i = 1; i <= scc_cnt; ++i) {
        if(!out[i]) {
            ++ans;
            flag = i;
        }
    }
    if(ans == 1) printf("%d\n", scc_num[flag]);
    else printf("0\n");
    return 0;
}

 

上一篇:杀人游戏(tarjan思维好题)


下一篇:hdu4685 Prince and Princess(tarjan强连通分量+二分图匹配)