POJ2186(强连通分量分解)
2024-10-18 18:19:07
Popular Cows
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 35035 | Accepted: 14278 |
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
题意:求从其他所有顶点都可以到达的顶点数目。
思路:所求顶点数目即为拓扑序最后的强连通分量中的顶点数目,检查其他点是否都可以到达该强连通分量。
//2017-08-20
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector> using namespace std; const int N = ;
vector<int> G[N];//邻接表存图
vector<int> rG[N];//存反向图
vector<int> vs;//后序遍历顺序的顶点列表
bool vis[N];
int cmp[N];//所属强连通分量的拓扑序 void add_edge(int u, int v){
G[u].push_back(v);
rG[v].push_back(u);
} //input: u 顶点
//output: vs 后序遍历顺序的顶点列表
void dfs(int u){
vis[u] = true;
for(int i = ; i < G[u].size(); i++){
int v = G[u][i];
if(!vis[v])
dfs(v);
}
vs.push_back(u);
} //input: u 顶点编号; k 拓扑序号
//output: cmp[] 强连通分量拓扑序
void rdfs(int u, int k){
vis[u] = true;
cmp[u] = k;
for(int i = ; i < rG[u].size(); i++){
int v = rG[u][i];
if(!vis[v])
rdfs(v, k);
}
} //Strongly Connected Component 强连通分量
//input: n 顶点个数
//output: k 强连通分量数;
int scc(int n){
memset(vis, , sizeof(vis));
vs.clear();
for(int u = ; u < n; u++)
if(!vis[u])
dfs(u);
int k = ;
memset(vis, , sizeof(vis));
for(int i = vs.size()-; i >= ; i--)
if(!vis[vs[i]])
rdfs(vs[i], k++);
return k;
} void solve(int n){
int k = scc(n);
int u = , ans = ;
for(int v = ; v < n; v++){
if(cmp[v] == k-){
u = v;
ans++;
}
}
memset(vis, , sizeof(vis));
rdfs(u, );
for(int i = ; i < n; i++){
if(!vis[i]){
ans = ;
break;
}
}
printf("%d\n", ans);
} int main()
{
int n, m;
while(scanf("%d%d", &n, &m)!=EOF){
int u, v;
for(int i = ; i < n; i++){
G[i].clear();
rG[i].clear();
}
while(m--){
scanf("%d%d", &u, &v);
u--; v--;
add_edge(u, v);
}
solve(n);
} return ;
}
最新文章
- [C#项目开源] MongoDB 可视化管理工具 (2011年10月-至今)
- Javascript优化细节:短路表达式
- ThinkPHP3.2.3整合smarty模板(一)
- ARM、Intel、MIPS处理器啥区别?看完全懂了
- 扫描二维码自动识别手机系统(Android/IOS)
- September 22nd 2016 Week 39th Thursday
- spring源码学习之路---IOC初探(二)
- 做mapx、ArcEngine的二次开发出现“没有注册类别 (异常来自 HRESULT:0x80040154 (REGDB_E_CLASSNOTREG)”
- 重构edit 和 new页面
- svn忽略target
- Windows 10 IoT Core Samples
- Package inputenc Error: Unicode char \u8: not set up for use with LaTeX.
- Hadoop学习笔记(3)——分布式环境搭建
- vc关于文件拷贝
- Linux 确定系统glibc版本
- IOS基础:深入理解Objective-c中@class的含义
- 定时跳转的两种方式(html + javaweb)
- Day3--------------目录文件的浏览、管理及维护
- LOV里的值直接引用系统里定义的值集的值,且具有值集的安全性控制
- MySQL如何系统学习