BZOJ 1051 [HAOI2006]受欢迎的牛:强联通分量【模板】

题目

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B,B喜欢C,那么A也喜欢C。牛栏里共有N 头奶牛,给定一些奶牛之间的爱慕关系,请你

算出有多少头奶牛可以当明星。

输入格式

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

第二行到第M + 1行:每行两个用空格分开的整数:A和B,表示A喜欢B

输出格式

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

说明/提示

【数据范围】

10%的数据N<=20, M<=50

30%的数据N<=1000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

题解

首先,在一个强联通分量里的奶牛,可以看成是一只奶牛。因为在这个强联通分量里,如果有一只奶牛喜欢一只分量外的奶牛A,那么所有分量内的奶牛也都喜欢A;如果有一只分量外的奶牛B喜欢分量内的任意一只奶牛,那么B就喜欢分量内的所有奶牛

所以先tarjan缩点,将原图变为DAG

显然,当且仅当这个DAG有且仅有一个出度为0的点时,存在受欢迎的奶牛,且受欢迎的奶牛都在这个出度为0的点上;其他情况(如出度为0的点有多个、图根本不连通等)均不存在受欢迎的奶牛

Code

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#define MAX_N 10005
#define MAX_M 50005

using namespace std;

int n, m, tot = 0, cnt = 0;
int a[MAX_M];
int b[MAX_M];
int dfn[MAX_N];
int low[MAX_N];
int scc[MAX_N];
int siz[MAX_N];
int deg[MAX_N];
bool vis[MAX_N];
vector<int> e[MAX_N];
stack<int> s;

void tarjan(int x) {
    dfn[x] = low[x] = ++tot;
    vis[x] = true;
    s.push(x);
    for (int i = 0; i < e[x].size(); i++) {
        int t = e[x][i];
        if (!dfn[t]) {
            tarjan(t);
            low[x] = min(low[x], low[t]);
        } else if (vis[t]) {
            low[x] = min(low[x], dfn[t]);
        }
    }
    if (dfn[x] == low[x]) {
        cnt++;
        for (int t = 0; t != x;) {
            t = s.top();
            s.pop();
            vis[t] = false;
            siz[scc[t] = cnt]++;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", a + i, b + i);
        e[a[i]].push_back(b[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    for (int i = 1; i <= m; i++) {
        if (scc[a[i]] != scc[b[i]]) {
            deg[scc[a[i]]]++;
        }
    }
    int id = 0;
    for (int i = 1; i <= cnt; i++) {
        if (!deg[i]) {
            if (id) {
                printf("0\n");
                return 0;
            } else {
                id = i;
            }
        }
    }
    printf("%d\n", siz[id]);
}
点赞

发表评论

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