3月份一个偶然的机会刷了一道算法题，当时折腾了好久，趁现在有空赶紧记录一下。
原题地址：Rust&Murderer

题目描述

Detective Rust is investigating a homicide and he wants to chase down the murderer. The murderer knows he would definitely get caught if he takes the main roads for fleeing, so he uses the village roads (or side lanes) for running away from the crime scene.

Rust knows that the murderer will take village roads and he wants to chase him down. He is observing the city map, but it doesn't show the village roads (or side lanes) on it and shows only the main roads.

The map of the city is a graph consisting nodes (labeled to ) where a specific given node represents the current position of Rust and the rest of the nodes denote other places in the city, and an edge between two nodes is a main road between two places in the city. It can be suitably assumed that an edge that doesn't exist/isn't shown on the map is a village road (side lane). That means, there is a village road between two nodes and iff(if and only if) there is no city road between them.

Rust wants to calculate the shortest distance from his position (Node ) to all the other places in the city if he travels using the village roads (side lanes).

Note: The graph/map of the city is ensured to be a sparse graph.

分析

问题本质上就是给定一个无权无向图，从S点出发，只能走不连通的路径(side lane)，求S点到每个点的最短路径。

• 基础思路是：用一个map存储所有的不连通的路径，然后用最短路径算法求出S点到每个点的路径。但是注意原始图是一个稀疏图，存储不连通的路径的话不会卡时间但是会卡空间。
• 因为是无权图，不需要用Dijkstra算法，直接BFS即可。BFS的方法就是用一个队列来存储每一层的结点，就像二叉树的层次遍历那样。
• 每次执行BFS时，从S出发，每下降一层距离就加1 。 关键是怎么知道某个节点到哪些节点不连通。为了解决卡空间的问题，可以构造一个hashset来存储没有访问过的节点。每次从这个hashset里遍历，看是不是连通。这样就OK了。

代码实现

#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int caseNumber;
    cin >> caseNumber;
    for (int i = 0; i < caseNumber; i ++){
        int cityNumber;
        int pathNumber;
        cin >> cityNumber >> pathNumber;

        unordered_map<int, unordered_set<int> > mainPath;
        unordered_set<int> unvisitedCities;

        for (int j = 1; j < cityNumber + 1; j ++){
            unvisitedCities.insert(j);
        }
       
        for (int j = 0; j < pathNumber; j ++){
            int src;
            int dst;
            cin >> src >> dst;
            mainPath[src].insert(dst);
            mainPath[dst].insert(src);
        }
       
        int derectiveLocation;
        cin >> derectiveLocation;
        int distance[cityNumber + 1];
        for (int j = 0; j < cityNumber + 1; j ++)
            distance[j] = -1;
        distance[derectiveLocation] = 0;
        queue<int> bfsQueue;

        bfsQueue.push(derectiveLocation);

        while (bfsQueue.size() && unvisitedCities.size()){
            int front = bfsQueue.front();
            unordered_set<int> tempSet(unvisitedCities);
            for (auto p : mainPath[front]){
                tempSet.erase(p);
            }
            for (auto index : tempSet) {
                if (distance[index] == -1) {
                    bfsQueue.push(index);
                    distance[index] = distance[front] + 1;
                }
            }
            for (auto c : tempSet){
                unvisitedCities.erase(c);
            } 
            bfsQueue.pop();
        }
        int realDistance[cityNumber ];
        for (int j = 1; j < derectiveLocation; j ++){
            realDistance[j] = distance[j];
        }
        for (int j = derectiveLocation + 1; j < cityNumber + 1; j ++){
            realDistance[j - 1] = distance[j];
        }
        printf("%d", realDistance[1]);
        for (int j = 2; j < cityNumber; j ++){
            printf(" %d", realDistance[j]);
        }
        printf("\n");
    }
    return 0;
}