美文网首页
[33]重要节点-美团点评2018秋

[33]重要节点-美团点评2018秋

作者: jdzhangxin | 来源:发表于2018-11-08 19:49 被阅读13次

    1.题目描述

    给出一张有向图G(V,E),所有的边都是有向边。对于图上的一个点v,从v出发可以到达的点的集合记为S_v,特别地,vS_v。再定义一个点的集合T_v:从T_v中的任意一个点出发,可以达到点v,特别地,vT_v,。简而言之,S_vv能到的点的集合,而T_v是能到v的点的集合。
    如果对于一个点v,如果T_v中的点数严格大于S_v中的点数,那么v就是一个重要节点。输入一张图,输出图中重要节点的个数。

    • 输入描述:
      第一行输入两个数n,m(1n,m1000),分别表示点数和边数。
      接下来m行,每行两个数uv。表示一条从uv的有向边,输入中可能存在重边和自环。(1u,vn)
    • 输出描述:
      输出一个数,重要节点的个数。
    • 输入示例:
      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;
    }
    

    牛课题目

    相关文章

      网友评论

          本文标题:[33]重要节点-美团点评2018秋

          本文链接:https://www.haomeiwen.com/subject/wvtpoftx.html