每一头牛的愿望就是变成一头最受欢迎的牛。

现在有 N 头牛,编号从 1 到 N,给你 M 对整数 (A,B),表示牛 A 认为牛 B 受欢迎。

这种关系是具有传递性的,如果 A 认为 B 受欢迎,B 认为 C 受欢迎,那么牛 A 也认为牛 C 受欢迎。

你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。

输入格式

第一行两个数 N, M;

接下来 M 行,每行两个数 A, B,意思是 A 认为 B 是受欢迎的(给出的信息有可能重复,即有可能出现多个 A, B)。

输出格式

输出被除自己之外的所有牛认为是受欢迎的牛的数量。

数据范围 1≤N≤104, 1≤M≤5×104

输入样例:

3 3
1 2
2 1
2 3

输出样例:

1

代码实现

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int N = 1e4 + 10, M = 5e4 + 10;

int n, m, h[N], e[M], ne[M], idx, timestamp, dfn[N], low[N], ssc_cnt, id[N], Cnt[N], dout[N];
bool in_sk[N];
stack <int> sk;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int p) {

    dfn[p] = low[p] = ++timestamp;
    sk.push(p), in_sk[p] = 1;
    for(int i = h[p]; ~i; i = ne[i]) {
        int j = e[i];
        if(!dfn[j]) {
            tarjan(j);
            low[p] = min(low[p], low[j]);
        }
        else if (in_sk[j])
            low[p] = min(low[p],dfn[j]);
    }

    if(low[p] == dfn[p]) {
        int y;
        ++ssc_cnt;
        do {
            y = sk.top(); sk.pop();
            in_sk[y] = 0;
            id[y] = ssc_cnt;
            ++Cnt[ssc_cnt];
        }while(y != p);

    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--) {
        int a, b;
        cin >> a >> b;
        add(a,b);
    }
    for(int i = 1; i <= n; ++i)
        if(!dfn[i]) tarjan(i);

    for(int i = 1; i <= n; ++i)
        for(int j = h[i]; ~j; j = ne[j]) {
            int u = e[j];
            if(id[i] != id[u]) ++dout[id[i]];
        }

    int zeros = 0, sum = 0;
    for(int i = 1; i <= ssc_cnt; ++i) {
        if(!dout[i]) {
            sum += Cnt[i];
            ++zeros;
        }
        if(zeros > 1) {
            sum = 0;
            break;
        }
    }
    cout << sum;
    return 0;
} 
分类: Tarjan

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status