解题思路

这是一个图论问题，需要找出重要节点的数量。重要节点的定义是：

  1. 对于节点 ，定义 为从 出发可以到达的点的集合（包括 自身）
  2. 定义 为能到达 的点的集合（包括 自身）
  3. 如果 中的点数严格大于 中的点数，则 是重要节点

解决方案：

  1. 对每个点 进行 BFS，找出从 能到达的所有点（构建 ）
  2. 同时统计每个点能被多少个点到达（构建 ）
  3. 最后比较每个点的入度和出度，入度大于出度的点即为重要节点

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m, u, v;
    while(cin >> n >> m) {
        // 建图
        vector<vector<int>> g(n+1);
        for(int i = 0; i < m; ++i) {
            cin >> u >> v;
            g[u].push_back(v);
        }
        
        // 计算每个点的可达性
        vector<vector<bool>> vis(n+1, vector<bool>(n+1, false));
        vector<int> in(n+1), out(n+1);
        
        // 对每个点进行BFS
        for(int i = 1; i <= n; ++i) {
            queue<int> q;
            q.push(i);
            vis[i][i] = true;
            
            while(!q.empty()) {
                int curr = q.front();
                q.pop();
                
                for(int& next : g[curr]) {
                    if(!vis[i][next]) {
                        vis[i][next] = true;
                        out[i]++;    // i能到达的点数
                        in[next]++;  // 能到达next的点数
                        q.push(next);
                    }
                }
            }
        }
        
        // 统计重要节点
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            if(in[i] > out[i]) cnt++;
        }
        
        cout << cnt << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            
            // 建图
            List<List<Integer>> g = new ArrayList<>(n + 1);
            for(int i = 0; i <= n; i++) {
                g.add(new ArrayList<>());
            }
            
            for(int i = 0; i < m; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                g.get(u).add(v);
            }
            
            // 计算每个点的可达性
            boolean[][] vis = new boolean[n + 1][n + 1];
            int[] in = new int[n + 1];
            int[] out = new int[n + 1];
            
            // 对每个点进行BFS
            for(int i = 1; i <= n; i++) {
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                vis[i][i] = true;
                
                while(!q.isEmpty()) {
                    int curr = q.poll();
                    
                    for(int next : g.get(curr)) {
                        if(!vis[i][next]) {
                            vis[i][next] = true;
                            out[i]++;
                            in[next]++;
                            q.offer(next);
                        }
                    }
                }
            }
            
            // 统计重要节点
            int cnt = 0;
            for(int i = 1; i <= n; i++) {
                if(in[i] > out[i]) cnt++;
            }
            
            System.out.println(cnt);
        }
    }
}

from collections import deque

def solve():
    while True:
        try:
            n, m = map(int, input().split())
            
            # 建图
            g = [[] for _ in range(n + 1)]
            for _ in range(m):
                u, v = map(int, input().split())
                g[u].append(v)
            
            # 计算每个点的可达性
            vis = [[False] * (n + 1) for _ in range(n + 1)]
            in_deg = [0] * (n + 1)
            out_deg = [0] * (n + 1)
            
            # 对每个点进行BFS
            for i in range(1, n + 1):
                q = deque([i])
                vis[i][i] = True
                
                while q:
                    curr = q.popleft()
                    
                    for next_node in g[curr]:
                        if not vis[i][next_node]:
                            vis[i][next_node] = True
                            out_deg[i] += 1
                            in_deg[next_node] += 1
                            q.append(next_node)
            
            # 统计重要节点
            cnt = sum(1 for i in range(1, n + 1) if in_deg[i] > out_deg[i])
            print(cnt)
            
        except EOFError:
            break

solve()

算法及复杂度

  • 算法：BFS（广度优先搜索）
  • 时间复杂度： - 对每个点都需要进行一次BFS
  • 空间复杂度： - 需要存储可达性矩阵