jiaowubuaa_acm题

jiaowubuaa_acm题每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛,编号从 1 到 N,给你 M 对整数 (A,B),表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的,如果 A 认为 B 受欢迎,B 认为 C 受欢迎,那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。输入格式第一行两个数 N,M;接下来 M 行,每行两个数 A,B,意思是 A 认为 B 是受欢迎的(给出的信息有可能重复,即有可能出现多个 A,B)。输出格式输出被除自己之外的所有牛认为是

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

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

现在有 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

样例解释
只有第三头牛被除自己之外的所有牛认为是受欢迎的。

题解
Tarjan

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int M = 5e4 + 10;
struct Edge{ 

int v,next,w;
}edge[M];
int head[N],cnt;
int low[N],num[N],dfn;
int sccno[N],sta[N],bcc,top;
bool in_stack[N];
int out[N],Size[N];
void add(int u,int v){ 

edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void Tarjan(int u){ 

low[u] = num[u] = ++ dfn;
sta[top ++] = u,in_stack[u] = true;
for(int i = head[u];~i;i = edge[i].next){ 

int v = edge[i].v;
if(!num[v]){ 

Tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(in_stack[v])
low[u] = min(low[u],num[v]);
}
if(low[u] == num[u]){ 

bcc ++;
int t;
do{ 

Size[bcc] ++;
t = sta[-- top];
in_stack[t] = false;
sccno[t] = bcc;
}while(t != u);
}
}
int main(){ 

memset(head,-1,sizeof head);
int n,m;
cin>>n>>m;
int x,y;
for(int i = 0;i < m;i ++){ 

cin>>x>>y;
add(x,y);
}
for(int i = 1;i <= n;i ++){ 

if(!num[i])Tarjan(i);
}
for(int i = 1;i <= n;i ++){ 

for(int j = head[i];~j;j = edge[j].next){ 

int a = sccno[i],b = sccno[edge[j].v];
if(a != b)out[a] ++;
}
}
int count = 0;
int c = 0;
for(int i = 1;i <= bcc;i ++){ 

if(!out[i]){ 

c ++;
count += Size[i];
}
}
if(c == 1)cout<<count<<endl;
else cout<<0<<endl;
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168619.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • IDEA使用教程_intellij idea使用教程

    IDEA使用教程_intellij idea使用教程idea启动后会在cpan当前用户下生成一个C:\Users\Crystal.IntelliJIdea2018.1文件夹,这个文件夹里面有两个子文件夹config和system。删除这两个文件夹,idea在启动时候会重新配置。idea的project类似于eclipse的workspace;idea的modue类似于eclipse的project;配置都是在setti…

    2022年10月13日
  • 会议室预定功能_高校会议室预订系统功能简介

    会议室预定功能_高校会议室预订系统功能简介一、功能介绍这是一个基于前端页面js代码的动态效果和后端对数据库数据更新的操作,主要实现的是会议室的预定功能,当员工进入预定页面后可以看到某天的某个会议室的某个时段是否被预定,当没被预定的情况下,就

  • java代码生成器,springboot代码生成器—增加更新,查询功能(持续更新)

    java代码生成器,springboot代码生成器—增加更新,查询功能(持续更新)时隔一周多,今天终于抽出时间来更新一波代码生成器,最近公司让我研究rpa,弄得焦头烂额的,话不多说,进入正题。之前有朋友让我讲一下代码生成器的原理,这篇博客就大体描述一下,以后慢慢细致讲解。双击codeMan.exe,众所周知,java做成exe程序很麻烦,在这里我是利用了.net的ikvm插件把jar包直接编译成了exe程序,这个启动界面会连接我的服务器,去检查版本更新,如果有更新就会在…

  • VS2008安装失败_vs2015无法安装

    VS2008安装失败_vs2015无法安装虽然我搞了很多年的java,现在由于工作需要又要转到.net上做研究工作,以前用vb那会对ms没有什么好感,之后用过vs.net的第一个版本做开发,本以为安装一下vs2008的开发环境应该是小菜一碟,没想到经历这么曲折,赶紧写下来为同行参考。 虽然做程序开发的时间有些年头了,但是对最新的技术和工具等还总是保持着关心,vs2008中文90天试用版刚从ms网站上放出来时我就下载安装过,当时很顺

  • pycharm如何分段运行_pycharm只运行部分代码

    pycharm如何分段运行_pycharm只运行部分代码在最新版的pycharm中拥有类似jupyter的分段执行代码功能,其使用方法如下:1.在想要分段运行的段前一行(空白行)输入#%%2.选择Usescientificmode3.分段运行的结果补充知识:Pycharm分行或分块执行介绍Pycharm中其实也可以使用类似于Spyder和Jupyter中的分行或分块执行,主要可以使用两种方法。需要注意的是,下面两种方法的本质都是在控制台执行,要注意…

  • 关于大学计算机相关专业学习路线的见解与分析

    关于大学计算机相关专业学习路线的见解与分析谨以此文献给仍然迷失在大学生活中的计算机专业学子!!!不管你是如何选择了这门专业,我想告诉你的是这是一个很深的领域,没有热爱不如尽早转行。根据百度百科计算机科学与技术专业(以下简称计算机专业)给出的描述,该专业的主干课程有算法、数据结构、操作系统、编译原理、计算机组成原理、计算机体系结构、计算机网络(划重点,这些都是专业基础课,其中的任意一门拿出来都够研究一生的,虽然大学的教育基本上都是讲…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号