题解 | #旅行牛#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <queue>
#include <valarray>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return bool布尔型
     */
    bool hasCycle(ListNode* head) {
        // write code here
        map<int, set<int>> ingraph;
        map<int, set<int>> outgraph;
        // vector<int> degree(10E4+1, 0);
        int pk = head->val;
        int pk1 = head->val;
        head = head->next;
        if(!head) return false;
        while(head){
            pk = head->val;
            if(pk == pk1) return true;
            outgraph[pk1].insert(pk);   // pk1 -> pk // 记录出去
            ingraph[pk].insert(pk1);
            head = head->next;
            pk1 = pk;
        }

        while(!ingraph.empty())
        {
            // for(auto it:ingraph){
            // 遍历，每次删除入度为1的数字
            queue<int> q;
            for(auto it:ingraph){
                if (it.second.size() == 1){
                    // 调整其他节点的入度
                    if(outgraph.find(it.first) != outgraph.end()){
                        for(auto outs:outgraph[it.first]){
                            ingraph[outs].erase(it.first);
                        }
                    }
                    // 删除该节点
                    q.push(it.first);
                }
            }
            if(q.empty()) return false;
            else{
                while(!q.empty())
                {
                    ingraph.erase(q.front());
                    q.pop();
                }
            }

        }

        return true;
    }
};