POJ——T2186 Popular Cows || 洛谷——P2341 [HAOI2006]受欢迎的牛
2024-10-01 11:16:49
http://poj.org/problem?id=2186
||
https://www.luogu.org/problem/show?pid=2341
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 33470 | Accepted: 13634 |
Description
Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.
Input
* Line 1: Two space-separated integers, N and M
* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.
Output
* Line 1: A single integer that is the number of cows who are considered popular by every other cow.
Sample Input
3 3
1 2
2 1
2 3
Sample Output
1
Hint
Cow 3 is the only cow of high popularity.
Source
tarjan缩点,输出出度为0的点的子图中的点的个数
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std; const int N();
int n,m,u,v,sumchudu,ans,cnt;
int point[N],chudu[N];
int sumedge,head[N];
struct Edge
{
int from,to,next;
Edge(int from=,int to=,int next=) :
from(from),to(to),next(next) {}
}edge[N]; int ins(int from,int to)
{
edge[++sumedge]=Edge(from,to,head[from]);
return head[from]=sumedge;
} int dfn[N],low[N],tim;
int Stack[N],top,instack[N];
int col[N],sumcol; void DFS(int now)
{
dfn[now]=low[now]= ++tim;
Stack[++top]=now; instack[now]=;
for(int i=head[now];i;i=edge[i].next)
{
v=edge[i].to;
if(instack[v]) low[now]=min(low[now],dfn[v]);
else if(!dfn[v])
DFS(v), low[now]=min(low[now],low[v]);
}
if(low[now]==dfn[now])
{
col[now]= ++sumcol;
point[sumcol]++;
for(;Stack[top]!=now;top--)
{
point[sumcol]++;
col[Stack[top]]=sumcol;
instack[Stack[top]]=;
}
instack[now]=; top--;
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d%d",&u,&v),ins(u,v);
for(int i=;i<=n;i++)
if(!dfn[i]) DFS(i);
for(int i=;i<=m;i++)
{
u=edge[i].from; v=edge[i].to;
if(col[u]!=col[v]) chudu[col[u]]++;
}
for(int i=;i<=sumcol;i++) if(!chudu[i])
++sumchudu,ans=point[i];
if(sumchudu!=) ans=;
printf("%d\n",ans);
return ;
}
最新文章
- Linux基础命令介绍七:网络传输与安全 wget curl rsync iptables
- easyui datagrid 的分页刷新按钮
- yahoo 交易数据
- RxJava开发精要6 – Observables组合
- Android学习总结——实现Home键功能
- 每日一帖示例程序(使用TWebBrowser基于HTML做)
- Angular:Reactive Form的使用方法和自定义验证器
- docker报错:Get https://registry-1.docker.io/v2/: net/http: request canceled while waiting for connection (Client.Timeout exceeded while awaiting headers)
- 大众美团服务链监控CAT
- 60道Python面试题&;答案精选!找工作前必看
- centos设置网卡开机自启动
- poj 3641 快速幂
- HTTP与HTTPs的区别?
- PostegreSQL模板数据库
- Android倒计时功能的实现
- Linux下高并发socket最大连接数所受的各种限制(转)
- OS之进程管理---进程调度和多线程调度
- Python3之hashlib
- Ubuntu和centos下查看包的安装路径
- openAI最近推出了一个新的语言模型 ";GPT-2";