网站集约建设后网站域名规范,吉林建筑信息平台,网站打开速度慢是否需要升级带宽,公司简介ppt案例题目背景
本题测试数据已修复。
题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂#xff0c;每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 AAA 喜欢 BBB#xff0c;BBB 喜欢 CCC#xff0c;那么…题目背景
本题测试数据已修复。
题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 AAA 喜欢 BBBBBB 喜欢 CCC那么 AAA 也喜欢 CCC。牛栏里共有 NNN 头奶牛给定一些奶牛之间的爱慕关系请你算出有多少头奶牛可以当明星。
输入格式
第一行两个用空格分开的整数NNN 和 MMM。
接下来 MMM 行每行两个用空格分开的整数AAA 和 BBB表示 AAA 喜欢 BBB。
输出格式
一行单独一个整数表示明星奶牛的数量。
样例 #1
样例输入 #1
3 3
1 2
2 1
2 3样例输出 #1
1提示
只有 333 号奶牛可以做明星。
【数据范围】
对于 10%10\%10% 的数据N≤20N\le20N≤20M≤50M\le50M≤50。
对于 30%30\%30% 的数据N≤103N\le10^3N≤103M≤2×104M\le2\times 10^4M≤2×104。
对于 70%70\%70% 的数据N≤5×103N\le5\times 10^3N≤5×103M≤5×104M\le5\times 10^4M≤5×104。
对于 100%100\%100% 的数据1≤N≤1041\le N\le10^41≤N≤1041≤M≤5×1041\le M\le5\times 10^41≤M≤5×104。
解题思路
根据题意中的“喜欢可以传递”在一个爱慕环中的奶牛可以缩成一头奶牛
因为环中任何一头奶牛所喜欢的也被环中其他的奶牛喜欢
喜欢环中任何一头奶牛也会喜欢环中所有的奶牛
采用tarjan缩点生成一张新图图中的所有奶牛都是“单相思”
只有图中出度为000的节点可能是明星奶牛
因为“单相思”不会得到回应也就不会符合“被所有奶牛喜欢”这一条件
但是如果有多个出度为000的节点那么就不存在明星奶牛因为出度为000的奶牛不会互相喜欢
AC代码如下
#include iostream
#include string.h
#include queue
using namespace std;
const int max_n 1e4;
const int max_m 5e4;int n, m, u, v;
//链式前向星
int head[max_n 1];
int tot -1;
struct edge { int v, next; }edges[max_m];
//tarjan缩点
int timeclock 0, dfn[max_n 1], low[max_n 1];
int in_stack[max_n 1], stack[max_n], rsp -1;
//新图
int belong[max_n 1], power[max_n 1], cnt 0;
int out[max_n 1];//入度void add_edge(int u, int v) {edges[tot] { v, head[u] }; head[u] tot;
}void tarjan(int s) {dfn[s] low[s] timeclock;stack[rsp] s;in_stack[s] 1;for (int i head[s]; i ! -1; i edges[i].next) {int v edges[i].v;if (!dfn[v]) {tarjan(v);low[s] min(low[s], low[v]);}else if (in_stack[v]) {low[s] min(low[s], low[v]);}}if (dfn[s] low[s]) {cnt;while (stack[rsp 1] ! s) {belong[stack[rsp]] cnt;power[cnt];//记录合并节点的数量in_stack[stack[rsp]] 0;rsp--;}}
}int main() {memset(head 1, -1, sizeof(int) * max_n);cin n m;for (int i 0; i m; i) {cin u v;add_edge(u, v);}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 edges[j].next) {int v edges[j].v;//出度计数if (belong[i] ! belong[v]) {out[belong[i]];}}}int ans 0, find 0;for (int i 1; i cnt; i) {if (!out[i]) {if (find) {cout 0 endl;return 0;}else {find;ans i;}}}cout power[ans] endl;return 0;
}
