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;
}
