有没有大佬帮忙看看这个在考什么，今天的面试题没写出来

nlnlnl

   1.小Q最近在玩一个嵌入式开发板，看着板子上的一堆电容，他想比较板子上电容数量的多少。第一行给定比较次数n，
     接下来n行，每行给定两个板子的编号a1,a2,编号从1开始。每行第一个元素a1为第一次比较中板子上电容数量较多的
     板子编号，第二个元素a2为板子上电容数量较少的板子编号。最后一行为要比较的两块板子的编号a,b.请返回这两块
     板子上电容数量大小的关系，若a更多返回1，b更多返回-1，无法判断返回0。输入数据保证合法，不会有矛盾的情况出现。


     样例输入如下：

     4                   //比较次数

     1  2

     2  4

     1  3

     4  3

     2  3


    样例输出：

    1

Croper

有向无环图的顶点连通性问题，或者说对有向无环图上的两顶点进行拓扑定序
思路：拓扑排序，确定先后，然后从拓扑次序靠前的点开始进行深度遍历，如果不能遍历到靠后的点说明不能确定，否则就能确定
一会来上代码

nlnlnl

Croper 发表于 2019-4-3 20:41
有向无环图的顶点连通性问题，或者说对有向无环图上的两顶点进行拓扑定序
思路：拓扑排序，确定先后，然后 ...

唉，拓扑排序没怎么看，不会，只能去补补了。

Croper

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;
 
struct node {
        int order;
        int indegree;
        vector<node*> nexts;
        node() :order(-1),indegree(0) {};
};

int isPre(vector<pair<int, int>> givenorder, pair<int, int> question) {  //主函数
        unordered_map<int, node*> map;          //这里使用map来记录节点是为了防止题目直接出现65536号节点之类的奇葩输入，导致建立了65536个节点而浪费大量内存
        unordered_set<node*> roots;             

        //遍历给出的路径，生成图，并将入度为零的节点放入root中
        for (auto path : givenorder) {          
                node*& pre = map[path.first];
                node*& next = map[path.second];
                if (pre == nullptr) {               //如果路径上的节点第一次出现则创建节点
                        pre = new node;                
                        roots.insert(pre);               //新创建的前方节点入度一定为0
                }
                if (next==nullptr) {
                        next = new node;
                        roots.insert(next);
                }
                
                roots.erase(next);                 //位于后方节点当然不可能入度为0了
                next->indegree++;
                pre->nexts.emplace_back(next);      
        }

       //如果询问的节点根本没有在条件中出现过那么一定无法判断先后
        node* p1 = map[question.first];
        node* p2 = map[question.second];
        if (p1 == nullptr || p2 == nullptr) return 0;  
        
         //拓扑排序
        //遍历方式：检查每个root中的节点，为其赋予唯一的顺序（因为没有节点比它更靠前了）
        //将其移除root，并将其子节点的indegree-1，如果indegree为0，则将其加入root
          //此方法将遍历所有非环上的节点， 
        int order = 0;
        while (!roots.empty()){                      
                node* pre = *(roots.begin());                                                                                                                                                                 
                roots.erase(pre);
                pre->order = order++;
                for (node* next : pre->nexts) {
                        next->indegree--;
                        if (next->indegree == 0) {
                                roots.insert(next);
                        }
                }
        };

        if (p1->order == -1 || p2->order == -1) return 0;   //这句可以不要，如果order==-1说明节点在环上，但题目明确了这是无环图
        
         //将p1重新定向为拓扑排序靠前的节点，p2为靠后的节点
        //flg为是否经过换位的标志，也是预定的输出；
        int flg = 1;                                        
        if (p1->order > p2->order) {             
                auto tmp = p1;
                p1 = p2;
                p2 = tmp;
                flg = -1;
        }

        //将p1视为根节点，从p1开始进行深度优先遍历
        stack<node*> stk;
        p1->indegree = 1;
        stk.push(p1);
        while (!stk.empty()) {                      
                node* pre = stk.top();
                stk.pop();
                for (node* next : pre->nexts) {
                        if (next == p2) return flg;
                        if (next->indegree == 1) continue;          //如果遍历遇到p2，返回flg值
                        next->indegree = 1;
                        stk.push(next);
                }
        }

        return 0;                                    //没有遍历到p2，返回0
}

int main() {
        //读取数据
        int N;   
        vector<pair<int, int>> givenorder;    
        pair<int, int> question;
        cin >> N;
        for (int i = 0; i < N; ++i) {        
                pair<int, int> path;
                cin >> path.first >> path.second;
                givenorder.push_back(path);
        }
        cin >> question.first >> question.second;

        //计算
        int ret = isPre(givenorder, question);

        //输出结构
        cout << ret;

        system("pause");
}

实验了lz的用例和一个自己编的用例，没有问题
但不保证一定正确，如果发现什么问题，告诉我一下

Croper

还有一个方法就是不进行拓扑排序，直接建立图后就以给出的两个节点开始进行遍历，如果能遍历到对方，就为1或-1，否则等于0
这个方法写起来应该还简单一些，

。。。似乎也要快一些，因为拓扑排序是遍历了所有节点，而这个方法不需要遍历所有节点

。。嗯。。。不过最好的方法似乎应该是在拓扑排序的时候遇到任意一个节点直接中断拓扑排序。。。。

Croper

修改如下

int isPre(vector<pair<int, int>> givenorder, pair<int, int> question) {  //主函数
        unordered_map<int, node*> map;          //这里使用map来记录节点是为了防止题目直接出现65536号节点之类的奇葩输入，导致建立了65536个节点而浪费大量内存
        unordered_set<node*> roots;

        //遍历给出的路径，生成图，并将入度为零的节点放入root中
        for (auto path : givenorder) {
                node*& pre = map[path.first];
                node*& next = map[path.second];
                if (pre == nullptr) {               //如果路径上的节点第一次出现则创建节点
                        pre = new node;
                        pre->id = path.first;
                        roots.insert(pre);               //新创建的前方节点入度一定为0
                }
                if (next == nullptr) {
                        next = new node;
                        next->id = path.second;
                        roots.insert(next);
                }

                roots.erase(next);                 //位于后方节点当然不可能入度为0了
                next->indegree++;
                pre->nexts.emplace_back(next);
        }

        //如果询问的节点根本没有在条件中出现过那么一定无法判断先后
        node* p1 = map[question.first];
        node* p2 = map[question.second];
        if (p1 == nullptr || p2 == nullptr) return 0;

        //拓扑排序
        //遍历方式：检查每个root中的节点，为其赋予唯一的顺序（因为没有节点比它更靠前了）
        //将其移除root，并将其子节点的indegree-1，如果indegree为0，则将其加入root
         //此方法将遍历所有非环上的节点， 
        int flg = 1;
        while (!roots.empty()) {
                node* pre = *(roots.begin());
                roots.erase(pre);
                for (node* next : pre->nexts) {
                        next->indegree--;
                        if (next->indegree == 0) {
                                if (next == p1 || next == p2) {
                                        if (next == p2) flg = -1;
                                        break;
                                }
                                roots.insert(next);
                        }
                }
        };

        //将p1重新定向为拓扑排序靠前的节点，p2为靠后的节点
   //flg为是否经过换位的标志，也是预定的输出；
        if (flg == -1) {
                auto tmp = p1;
                p1 = p2;
                p2 = tmp;
        }

        //将p1视为根节点，从p1开始进行深度优先遍历
        stack<node*> stk;
        unordered_map<node*, bool> hascheck;
        hascheck[p1] = true;
        stk.push(p1);
        while (!stk.empty()) {
                node* pre = stk.top();
                stk.pop();
                for (node* next : pre->nexts) {
                        if (next == p2) return flg;
                        if (hascheck[next]) continue;          //如果遍历遇到p2，返回flg值
                        hascheck[next] = true;
                        stk.push(next);
                }
        }

        return 0;                                    //没有遍历到p2，返回0
}