[Graphs] DFS.3- 1466. Reorder Routes to Make All Paths Lead to the City Zero

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/

Reorder Routes to Make All Paths Lead to the City Zero - LeetCode

 

• 난이도 : Midium
• 구하고자하는것:  Edge의 방향들이 0을 향하게 바꾼 횟수
• TC:  O(n)

---

1. 첫번쨰 방식.

class Solution {
public:
    set<vector<int>> roads; //std::set !! 이것은 무엇인가.. 꽤나 중요하고 방대해서 밑에 따로정리.
   // SET 왜 사용하는가? 빠른 검색 roads.find 로 O(logN)의 시간대로 검색할 수 있어 list 나 array
   //O(logN)의 시간대를 가지는것보다 빠름. SET을 사용함으로써 도로가 reorder되야하는지 재빠르게 알수있어
   //효율적임 
    unordered_map<int, vector<int>> graph; // hash, unordered_map을 사용한다 
    vector<bool> seen;
    
    int minReorder(int n, vector<vector<int>>& connections) {
        seen = vector(n, false);
        for (vector<int> edge: connections) {
            int x = edge[0], y = edge[1];
            graph[x].push_back(y);// bi connection 가정...
            graph[y].push_back(x);
            roads.insert({x, y});
        }
        
        seen[0] = true;
        return dfs(0);
    }
    
    int dfs(int node) {
        int ans = 0;
        for (int neighbor: graph[node]) {
            if (!seen[neighbor]) {
                if (roads.find({node, neighbor}) != roads.end()) {
                    ans++;
                }
                
                seen[neighbor] = true;
                ans += dfs(neighbor);
            }
        }
        
        return ans;
    }
};

** std::set **

https://ssocoit.tistory.com/41

[C++ STL] Set 사용설명서

• Set은 Key라고 불리는 원소들의 집합으로 이루어진 컨테이너  Key값들은 중복될 수 없음.
  또한 Set은 Key값의 순서대로 정렬 그리고 완전정렬. 이 말은 원소의 삽입 순서에 영향을 받지 않는다는 뜻
  (만약 정렬이 되지 않는 set을 원한다면 C++11부터 지원하는 unordered_set을 사용)
• Set은 Map과 동일하게 이진균형트리구조로 "검색, 삽입, 삭제"에는 평균 O(logN) Time complexity 소요.

---

<ChatGPT>This is an implementation of a solution to a problem that requires finding the minimum number of roads to reorder so that all cities in the road network are reachable from a specific city (city 0 in this case).
The algorithm uses a combination of a set (roads) and an unordered map (graph) to store information about the roads and their connections. The roads set stores the roads as pairs of connected cities, while the graph map stores the connections between each city and its neighboring cities.
The minReorder function initializes the seen vector, which is used to keep track of the cities that have been visited during the depth-first search (DFS). The function then returns the result of the dfs function, which performs the DFS starting from city 0.
The dfs function counts the number of roads that need to be reordered by checking if each neighbor of the current node has been visited. If a neighbor has not been visited, the roads set is used to determine if the road between the current node and the neighbor needs to be reordered. If so, the count is incremented. The function then recursively calls itself for the unvisited neighbor to continue the DFS.
Finally, the dfs function returns the number of reordered roads that it has found so far.

어우야 어렵다.? 정신있을떄 다시