【Luogu P2341】[USACO03FALL][HAOI2006]受欢迎的牛 G

Luogu P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$,$B$ 喜欢 $C$,那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛,给定一些奶牛之间的爱慕关系,请你算出有多少头奶牛可以当明星。

输入格式

第一行:两个用空格分开的整数:$N$ 和 $M$。

接下来 $M$ 行:每行两个用空格分开的整数:$A$ 和 $B$,表示 $A$ 喜欢 $B$。

输出格式

一行单独一个整数,表示明星奶牛的数量。

输入样例

3 3
1 2
2 1
2 3

输出样例

1

AC code

#include<stack>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const int MAXN = 1e5 + 5;

vector<int> grp[MAXN];
stack<int> sta;
int n, m, _time = 1, tmp, ans;
int vst[MAXN], low[MAXN];
int color[MAXN], totC, du[MAXN], cnt[MAXN];
bool insta[MAXN];
void dfs(int pos) {
    vst[pos] = low[pos] = _time++;
    sta.push(pos);
    insta[pos] = true;
    for(int i = 0;i < grp[pos].size(); ++i) {
        if(!vst[grp[pos][i]]) {
            dfs(grp[pos][i]);
            low[pos] = min(low[pos], low[grp[pos][i]]);
        }
        else if(insta[pos]) low[pos] = min(low[pos], low[grp[pos][i]]);
    }
    if(vst[pos] == low[pos]) {
        int las;
        totC++;
        do {
            //printf("%d ", sta.top());
            color[sta.top()] = totC;
            las = sta.top();
            sta.pop();
        } while(las != pos);
        //printf("\n");
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i) {
        int arg1, arg2;
        scanf("%d %d", &arg1, &arg2);
        arg1–;
        arg2–;
        grp[arg1].push_back(arg2);
    }
    for(int i = 0; i < n; ++i) if(!vst[i]) dfs(i);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < grp[i].size(); ++j) {
            if(color[grp[i][j]] != color[i]) du[color[i]]++;
        }
        cnt[color[i]]++;
    }
    for(int i = 1;i <= totC; ++i) {
        if(du[i] == 0) {
            tmp++;
            ans = cnt[i];
        }
    }
    if(tmp == 0) printf("0\n");
    else if(tmp > 1) printf("0\n");
    else printf("%d\n", ans);
    return 0;
}
点赞

发表评论

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