讨论/技术交流/4.21华为机试第二题:有向图/拓扑/
4.21华为机试第二题:有向图/拓扑

当时在现场用set通过了80%的用例,但实际上思路是不对的,今天仔细想了想用有向图临接表做了一下,但不知道这个是不是正解。
力扣:https://leetcode-cn.com/problems/route-between-nodes-lcci/ 这道题也是和机试第二题差不多思路的

#include<iostream>
#include<set>
#include<vector>
using namespace std;
class Solution {
public:
    bool finder = false;
    //搜索临接表
    void rearsh(vector<bool> & used,vector<set<int>> &near,int start){
        if(finder) return;
        if(near[start].empty()) return;
        used[start] = true;
        for(auto it = near[start].begin();it!=near[start].end();it++){
            if(used[*it]){
                finder = true;
                return;
            }
           else rearsh(used,near,*it);
        }
    }
    bool judgeExistLoop(int n, vector<set<int>>& near) {
        //使用过的数组
        vector<bool> used(n,false);
        for(int i=0;i<near.size();i++){
          rearsh(used,near,i);
          setFalse(used);
        }
        return finder;
    }
  //判断有几个无关模块
  int calculateEmpty(vector<int>& useless){
    int result = 0; 
    for(int i=0;i<useless.size();i++){
      if(useless[i]==0) result++;
    }
    return result;
  }
  
  void setFalse(vector<bool>& a){
    for(int i=0;i<a.size();i++) a[i] = false;
  }
};

int main() {
    Solution solute;
    vector<vector<int>> graph;
    //首先要输入有几个节点
    int N;
    scanf("%d",&N);
    //有几个指向关系
    int M;
    scanf("%d",&M);
    //建立临接表
    vector<set<int>> near(N);
    //无用模块
    vector<int> useless(N,0);
    for(int i=0;i<M;i++){
      int father;
      int son;
      scanf("%d %d",&father,&son);
      near[father].insert(son);
      useless[father] = 1;
      useless[son] = 1;
    }
    //总分十分,只要出现过环就扣两分,出现一个无关模块就扣一分,最低分为0
    int score = 10 - (solute.judgeExistLoop(N,near)?2:0) - solute.calculateEmpty(useless);
    if(score >= 0) cout<< score;
    else cout<< 0;
}

我用一个队列做出来的,主要思想就是广度优先搜索和一个set,然后先把第一个入队列,然后把与它相关的也加到队列里面,在把它弹出到set里面,然后遍历过去,如果子模块在set里面的话,就说明存在环,直接break循环就可以了。然后独立的模块(就那种既没有连接别人的,也没有被链接的模块)直接加上一个判断就好了。注意最低分为0.