【图论】Popular Cows
2024-08-22 04:43:21
[POJ2186]Popular Cows
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 34752 | Accepted: 14155 |
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就好了,输出其大小。(因为缩点后是DAG)
如果有>1个出度为0那么就肯定没有了。
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std; inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int MAXN=500001;
const int INF=999999;
int N,M;
int dfn[MAXN],low[MAXN];
int que[MAXN]; bool vis[MAXN];
vector<int> vec[MAXN];
int outdu[MAXN];
int tar[MAXN];
int tot,tmp,Col;
int size[MAXN]; void Tarjan(int x){
++tot; dfn[x]=low[x]=tot;
vis[x]=true; que[++tmp]=x;
for(int i=0;i<vec[x].size();i++){
int to=vec[x][i];
if(!dfn[to]){
Tarjan(to);
low[x]=min(low[x],low[to]);
}
else if(vis[to]) low[x]=min(dfn[to],low[x]);
}
if(dfn[x]==low[x]){
++Col; tar[x]=Col;
vis[x]=false;
while(que[tmp]!=x){
int k=que[tmp];
tar[k]=Col; vis[k]=false;
tmp--;
}
tmp--;
}
}
int ans,anst;
int main(){
N=read(),M=read();
for(int i=1;i<=M;i++){
int u=read(),v=read();
vec[u].push_back(v);
}
for(int i=1;i<=N;i++) if(!dfn[i]) Tarjan(i);
for(int i=1;i<=N;i++){
int col=tar[i];size[col]++;
for(int j=0;j<vec[i].size();j++){
if(tar[vec[i][j]]!=col)
outdu[col]++;
}
}
for(int i=1;i<=Col;i++){
if(!outdu[i])
ans+=size[i],anst++;
}
if(anst>1) printf("0\n");
else printf("%d\n",ans);
}
最新文章
- XP机器上WCF采用X509证书加密时IIS读取证书的授权
- cessss
- Centos配置国内yum源
- Android读取自定义View属性
- atitit.提升备份文件复制速度(4) ---数据挖掘 获取回收站文件列表
- iOS 自定义导航栏 和状态栏
- AOJ - 2224 Save your cat(最小生成树)
- Lua学习笔记(三):函数和闭包
- Android 按钮按下效果
- C#编辑基础笔记
- AFNetworking 关于JSON text did not start with array or object and option to allow fragments not set 错误
- CF Round#436 div2
- 关于linux内核驱动开发中Makefile编译的问题
- MySQL学习笔记(五)并发时经典常见的死锁原因及解决方法
- 【java】抽象类和接口区别
- python sphinx 文档自动生成方法
- easyui - 标签属性顺序要对 否则options 错误
- shell编程(三)之条件判断(if语句)
- Qt532.QSettings_默认分隔符
- Java代码优化,都有哪些常用方法?