1.题目描述
给出一张有向图G(V,E),所有的边都是有向边。对于图上的一个点v
,从v
出发可以到达的点的集合记为S_v
,特别地,v
∈S_v
。再定义一个点的集合T_v
:从T_v
中的任意一个点出发,可以达到点v
,特别地,v
∈T_v
,。简而言之,S_v
是v
能到的点的集合,而T_v
是能到v
的点的集合。
如果对于一个点v
,如果T_v
中的点数严格大于S_v
中的点数,那么v
就是一个重要节点。输入一张图,输出图中重要节点的个数。
- 输入描述:
第一行输入两个数n
,m
(1
≤n
,m
≤1000
),分别表示点数和边数。
接下来m
行,每行两个数u
,v
。表示一条从u
到v
的有向边,输入中可能存在重边和自环。(1
≤u
,v
≤n
) - 输出描述:
输出一个数,重要节点的个数。 - 输入示例:
4 3 2 1 3 1 1 4
- 输出示例:
2
2.题目解析
-
示例分析
V | S_v | T_v |
---|---|---|
1 | 1 | 2 |
2 | 1 | 0 |
3 | 1 | 0 |
4 | 0 | 3 |
3.参考答案
集合解法
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 0; // 顶点数
int m = 0; // 边数
scanf("%d%d", &n, &m);
vector<int> vec[n+1]; //以邻接表的形式存边,下标表示起点,数据表示终点
for (int i = 1; i <= m; i++) {
int u = 0; // 起点
int v = 0; // 终点
scanf("%d%d", &u, &v);
vec[u].push_back(v); // 保存关系
}
// BFS
set<int> S_v[n+1];
set<int> T_v[n+1];
for (int i = 1; i <= n; i++) { // 遍历顶点
queue<int> q;
q.push(i);
while (!q.empty()) {// 迭代方式BFS
int now = q.front();
q.pop();
for (int j = 0; j < vec[now].size(); j++) { // 遍历now的后续顶点
int post = vec[now][j];
if(S_v[i].count(post) == 0){
S_v[i].insert(post);
T_v[post].insert(i);
q.push(post); // 记录后续节点
}
}
}
}
// 统计结果
int ans = 0;
for (int i = 1; i <= n; i++) {
if (T_v[i].size() > S_v[i].size()) ans++;
}
//计算重要节点的数量
printf("%d\n", ans);
return 0;
}
使用set
内存超出
向量解法
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 0; // 顶点数
int m = 0; // 边数
scanf("%d%d", &n, &m);
vector<int> vec[n+1]; //以邻接表的形式存边,下标表示起点,数据表示终点
for (int i = 1; i <= m; i++) {
int u = 0; // 起点
int v = 0; // 终点
scanf("%d%d", &u, &v);
vec[u].push_back(v); // 保存关系
}
// BFS
vector<int> S_v[n+1];
vector<int> T_v[n+1];
for (int i = 1; i <= n; i++) { // 遍历顶点
queue<int> q;
q.push(i);
while (!q.empty()) {// 迭代方式BFS
int now = q.front();
q.pop();
for (int j = 0; j < vec[now].size(); j++) { // 遍历now的后续顶点
int post = vec[now][j];
if(find(S_v[i].begin(),S_v[i].end(),post) == S_v[i].end()){
S_v[i].push_back(post);
T_v[post].push_back(i);
q.push(post); // 记录后续节点
}
}
}
}
// 统计结果
int ans = 0;
for (int i = 1; i <= n; i++) {
if (T_v[i].size() > S_v[i].size()) ans++;
}
//计算重要节点的数量
printf("%d\n", ans);
return 0;
}
数组解法
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n = 0; // 顶点数
int m = 0; // 边数
scanf("%d%d", &n, &m);
vector<int> vec[n+1]; //以邻接表的形式存边,下标表示起点,数据表示终点
for (int i = 1; i <= m; i++) {
int u = 0; // 起点
int v = 0; // 终点
scanf("%d%d", &u, &v);
vec[u].push_back(v); // 保存关系
}
// BFS
queue<int> q;
int now;
bool ok[n + 1][n + 1]; // ok[i][j]为true表示i可以到达j;为false表示i不能到达j。默认值为false;
for(int i=0;i<=n;i++){
fill_n(ok[i],n+1,false);
}
for (int i = 1; i <= n; i++) { // 遍历顶点
q.push(i);
ok[i][i] = true;
while (!q.empty()) {// 迭代方式BFS
now = q.front();
q.pop();
for (int j = 0; j < vec[now].size(); j++) { // 遍历now的后续顶点
int post = vec[now][j];
if (!ok[i][post]) { // 默认false
ok[i][post] = true;
q.push(post); // 记录后续节点
}
}
}
}
// 统计
int numin[n+1]; // numin[i]储存能到达点i的点的数量
fill_n(numin,n+1,0);
int numout[n+1];// numout[i]储存点i能到达的点的数量
fill_n(numout,n+1,0);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (ok[i][j]) { // 如果存在累加
numin[j]++;
numout[i]++;
}
}
//根据 ok 数组记录计算每个点能达到的点数 和能达到每个点的点数
int ans = 0;
for (int i = 1; i <= n; i++) {
if (numin[i] > numout[i])
ans++;
}
//计算重要节点的数量
printf("%d\n", ans);
return 0;
}
网友评论