Leetcode 332 스케줄 재 설정 (오로라 경로 Hierholzer 알고리즘)

일부 예비 지식:

오로라 경로: 한 장의 그림 에서 한 점 에서 모든 변 을 옮 겨 다 닐 수 있다 면 옮 겨 다 니 는 과정 에서 이 경 로 를 오로라 경로 라 고 합 니 다.만약 이 경로 가 닫 힌 것 이 라면, 오 라 회 로 라 고 부른다.쉽게 말 하면 한 장의 그림 이 '한 획 의 그림' 이 될 수 있다 면 '한 획 의 그림' 의 그 궤적 을 오로라 경로 라 고 한다.

오 라 도 는 오 라 회 로 를 포함 한 그림 을 오 라 투 라 고 부 르 고 오 라 경 로 를 포함 한 그림 을 반 오 라 투 라 고 부른다.무 방향 그림 에서 모든 정점 의 도수 가 짝수 라면 오로라 그림 이다.두 개의 정점 이 있 는 도 수 는 홀수 이 고, 다른 것 은 짝수 이 며, 반 오로라 투 이다.방향 도 에 있 습 니 다. 모든 정점 의 입 도 는 출 도 와 같 으 면 오로라 투 입 니 다.만약 에 두 개의 정점 의 입 도 는 출 도와 같 지 않 고 다른 노드 의 입 도 는 초 독 과 같 으 면 반 오로라 그림 이다.한 장의 그림 에서 한 점 에서 모든 변 을 옮 겨 다 닐 수 있다 면 옮 겨 다 니 는 과정 에서 이 경 로 를 오로라 경로 라 고 합 니 다.만약 이 경로 가 닫 힌 것 이 라면, 오 라 회 로 라 고 부른다.쉽게 말 하면 한 장의 그림 이 '한 획 의 그림' 이 될 수 있다 면 '한 획 의 그림' 의 그 궤적 을 오로라 경로 라 고 한다.

Hierholzer 알고리즘: 해 결 된 문제: 방향 도 를 제시 하고 오로라 도 를 위해 오로라 회 로 를 구한다.알고리즘 흐름:

임 의 정점 을 기점 으로 모든 인접 한 곳 을 옮 겨 다 닌 다.

깊이 있 게 검색 하여 인접 한 정점 에 접근 합 니 다.지나 간 쪽 을 모두 삭제 합 니 다.

현재 정점 에 인접 한 곳 이 없 으 면 정점 을 창고 에 넣는다.

스 택 의 정점 역순 수출 은 바로 출발점 에서 출발 하 는 오 라 회 로 이다.

 성질 1: 이 그림 이 오로라 그림 이 라면 창고 바닥 은 반드시 출발점 이 될 것 이다.이 그림 이 반 오로라 그림 이 라면 스 택 밑 에 있 는 것 은 출발점 과 다른 또 다른 홀수 정점 입 니 다.
성질 2: 이 그림 이 오 라 도 (/ 반 오 라 도) 라면 스 택 의 바닥 에서 꼭대기 까지  정점 은 오 라 회 로 (/ 오 라 경로) 의 제 이다.  정점
 
제목 설명:
비행기 표를 지정 한 문자열 2 차원 배열 [from, to], 하위 배열 의 두 구성원 은 각각 비행기 가 출발 하고 착륙 하 는 공항 장 소 를 표시 하여 이 일정 을 재 계획 하고 정렬 합 니 다.이 모든 비행기 표 는 JFK (케네디 국제공항) 에서 출발 하 는 선생님 에 속 하기 때문에 JFK 에서 출발 해 야 합 니 다.다음 과 같은 세 가지 요구 가 있다.

여러 가지 효과 적 인 스케줄 이 존재 한다 면 문자 에 따라 가장 작은 스케줄 조합 으로 자 연 스 럽 게 정렬 할 수 있 습 니 다.예 를 들 어 스케줄 ["JFK", "LGA"] 는 ["JFK", "LGB"] 보다 작 고 정렬 이 앞 선다

.

모든 공항 은 세 개의 대문자 로 표시 된다.

모든 비행기 표 에 적어도 합 리 적 인 여정 이 존재 한다 고 가정 한다.

상기 요구 에 따라 사전 순서 가 비교적 작은 오로라 경 로 를 정리 하 다.
문제 풀이:
주의해 야 할 이 문 제 는 무 거 운 변 이 있 기 때문에 변 의 표 시 는 보통 01 로 표시 할 수 없다.비교적 우아 한 문법 은 unordered맵 은 인접 행렬 을 구축 하기 위해 맵 을 끼 워 넣 습 니 다.map 내 부 는 질서 가 있 습 니 다. 그러면 옮 겨 다 닐 때 사전 순서 가 작은 역 에 먼저 옮 겨 다 닙 니 다.그리고 Hierholzer 를 끼 워 서 오로라 경 로 를 구 했 으 면 좋 겠 어 요.
 
AC 코드:
두 개 붙 여 주세요. 첫 번 째 는 다른 사람의 코드 를 참고 하여 우아 해 졌 습 니 다.
두 번 째 는 자기 손 으로 비 벼 서 맵 의 끼 워 넣 기 를 원활 하 게 사용 하지 못 하고 인위적으로 순 서 를 매 기 느 라 많이 걸 렸 습 니 다.
 

class Solution {
public:
    // typedef map     
    typedef unordered_map<string,map<string,int>> adjacent;
    vector<string> ans;
    void euler(adjacent& adj,string now)
    {
        
        // map       &     conut           adj[now][next]
        for(auto & [next,count] : adj[now])
        {
            if(count >= 1)
            {
                // adj[now][next]--;
                count--;
                euler(adj,next);
            }
        }
        ans.push_back(now);
    }
    vector<string> findItinerary(vectorstring>>& tickets) {
        //                     
        // map unorder_map    
        //           
        // build_map
        adjacent adj;
        //   
        for(auto & t:tickets)
        {
            adj[t[0]][t[1]]++;
        }
        ans.clear();
        euler(adj,"JFK");
        reverse(ans.begin(),ans.end());
        return ans;
    }
  
};

 
 

class Solution {
public:
//TOPO
// str -> int
// int -> str
    int string_int(string s)
    {
        if(mp_str.find(s) != mp_str.end()) return mp_str[s];
        int id = mp_str.size();
        mp_str[s] = id;
        mp_int[id] = s;
        return id;
    }

    void euler(int pos)
    {
        int Len = edge[pos].size();
        sort(edge[pos].begin(),edge[pos].end());
        for(int i=0;i)
        {
            string next = edge[pos][i];
            if(vis[pos][mp_str[next]] >=1)
            {
                vis[pos][mp_str[next]]--;
                euler(mp_str[next]);
            }
        }
        ans.push_back(mp_int[pos]);
    }
    vector<string> findItinerary(vectorstring>>& tickets) {
        int Len = tickets.size();
        // build_map
        memset(vis,sizeof(vis),0);
        for(int i=0;i)
        {
            int from = string_int(tickets[i][0]);
            int to = string_int(tickets[i][1]);
            edge[from].push_back(tickets[i][1]);
            vis[from][to]++;
        }
        int city_counts = mp_str.size();
        
        ans.clear();
        euler(mp_str["JFK"]);
        reverse(ans.begin(),ans.end());
        return ans;
    }
private:
    map<string,int> mp_str;
    map<int,string> mp_int;
    vector<string> edge[10010];
    vector<string> ans;
    int vis[1010][1010];
};

 
 
몇 가지 생각:
1. 한 문 제 를 다 쓴 후에 만약 에 시간 or 공간의 복잡 도 순위 가 그다지 좋 지 않 으 면 다른 사람의 글 씨 를 보 러 가 야 한다.
2. 데이터 구 조 는 유연 하 게 사용 해 야 한다. 예전 의 방식 을 계속 사용 하지 말고 어떤 stl 도 구 를 사용 하면 효율 을 높 일 수 있 는 지 생각해 보 자.