顺丰01. 顺丰鄂州枢纽运转中心环线检测

顺丰XX杯第一题，说实话，当时看这个题目，可把我吓住了，当时看了背景晦涩难懂，就放弃了。现在再看看，真的有被无语到。

本来就是一道检查是否成环的问题，非凹一个背景上去，还是在第一题，一个字：绝！

思路：

回顾：以前刷leetcode的时候，有检查是否成环的问题，当时的题目时单链表成环，此类题型可以用两种方法解决：

一、用map<key,value>m，来存放<value,address>，如果找到的值所对应的address存在表示成环；

二、利用快慢指针，如果某时刻快指针与慢指针相遇，则此时必存在环；

正题：此题，可以看作多个“单链表”问题【不过需要自己手动构成链表】：需要自己一个一个去寻找合适的路径，并检查该路径上是否存在环。

如何模拟呢？

因为一个结点的指向可能有多个，所以用邻接表来存储每个结点的相邻结点。

如何判断呢？

通过判断，某个邻接表内的结点是否被访问过，如果访问过说明存在着环。

代码前注解：

1.利用map<key,value>m1作为结点访问结构，如果该结点访问过，则该节点对应的value为1；

2.利用map<key,vector<int>>m2来存储邻接表；

3.外部 利用 dfs 遍历每一个结点，内部 dfs 遍历每个结点相邻的结点。

代码：

class Solution {
public:
    unordered_map<int,int>visited;
    unordered_map<int,vector<int>>map;
    bool flag=false;
    void dfs(int x)
    {
        if(visited[x]==1){flag=true;return;}
        visited[x]=1;
        for(int y:map[x])
        {dfs(y);if(flag)return;}
        visited[x]=0;
        return;
    }
    bool hasCycle(string graph) {
    int n=graph.size();
    for(int i=0;i<n;i++)
    {
        int a=0,b=0;
        while(i<n&&graph[i]>='0'&&graph[i]<='9')
        {
            a*=10;
            a+=(graph[i]-'0');
            i++;
        }
        i+=2;// -> 为两个字符
        while(i<n&&graph[i]>='0'&&graph[i]<='9')
        {
            b*=10;
            b+=(graph[i]-'0');
            i++;
        }
        map[a].push_back(b);
    }
    for(int i=1;i<n;i++)
    {
        if(!visited[i])
        {
            dfs(i);
            if(flag)break;
        }
    }
       return flag;
    }
};

        此题应该还能用“拓扑排序”去解决，通过一层一层检查并删除 入度为0的结点，看最后是否存在入度为0的结点，如果存在就说明不存在环，如果不存在就说明存在环。

但是，目前一些佬哥们的做法，我还理解不了，等再熟悉点，换种方法再来解一下~