[Bzoj1051][HAOI2006]受欢迎的牛(tarjan)
2024-10-07 12:13:19
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1051
由题意可知,被所有牛仰慕的牛之间也互相仰慕,则最后的答案一定是唯一的强连通分量,如图:
且这个强连通分量出度为0。
所以用tarjan缩环,然后在判断出度为0的是否有且仅有一个点。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
struct node {
int e, next;
}edge[];
int head[maxn * ], len;
void add(int s, int e) {
edge[++len].e = e;
edge[len].next = head[s];
head[s] = len;
}
int color[maxn], dfn[maxn], low[maxn], vis[maxn];
int out[maxn];
int num[maxn];
int dfsnum, ansnum, top;
stack<int>q;
void tarjan(int x) {
dfn[x] = low[x] = ++dfsnum;
vis[x] = ;
q.push(x);
for (int i = head[x]; i; i = edge[i].next) {
int y = edge[i].e;
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (vis[y])
low[x] = min(low[x], dfn[y]);
}
if (low[x] == dfn[x]) {
ansnum++;
int y;
do {
y = q.top();
q.pop();
color[y] = ansnum;
num[ansnum]++;
vis[y] = ;
} while (x != y);
}
}
int main() {
int n, m, x, y;
scanf("%d%d", &n, &m);
for (int i = ; i <= m; i++) {
scanf("%d%d", &x, &y);
add(x, y);
}
for (int i = ; i <= n; i++)
if (!dfn[i])
tarjan(i);
for (int x = ; x <= n; x++) {
for (int i = head[x]; i; i = edge[i].next) {
int y = edge[i].e;
if (color[x] != color[y])
out[color[x]]++;
}
}
int ans = , f = ;
for (int i = ; i <= ansnum; i++)
if (out[i] == )ans = num[i], f++;
if (f == )
printf("%d\n", ans);
else
printf("0\n");
}
最新文章
- 按需加载.js .css文件
- 1002. A+B for Polynomials
- unity中全屏背景图缩放
- get/close not same thread Druid 连接池一个设置
- PHP抓取网络数据的6种常见方法
- cojs EX_香蕉 题解报告
- 揭秘淘宝自主研发的文件系统:TFS
- Bootstrap 按钮分组
- Python中__new__和__init__区别
- Java相关面试题总结+答案(三)
- 代码编辑器横评:为什么 VS Code 能拔得头筹
- pcntl_exec()
- java里的基本数据类型和引用数据类型
- PHPMailer出现SMTP connect() failed.
- 【Selenium-WebDriver自学】Log4J的设置(十五)
- 07_python_集合深浅拷贝
- PAT B1030 完美数列 (25 分)
- Java并发(二)-实现同步
- Ubuntu下 git 服务器的搭建【转】
- 同一页面的两个Iframe,其中一个iframe获取另一个iframe内的iframe中的元素值