leetcode 1042 인접 하지 않 은 꽃 염색 문제

7534 단어 알고리즘
1 부터 N 까지 의 표 시 를 누 르 면 N 개의 화원 이 있 습 니 다.모든 화원 에서 너 는 네 종류의 꽃 중 하 나 를 심 을 계획 이다.
paths [i] = [x, y] 는 화원 x 에서 화원 y 까지 의 양 방향 경 로 를 묘사 했다.
또 정원 에 들 어가 거나 떠 날 수 있 는 3 가지 이상 의 경로 가 없다.
당신 은 모든 화원 에 꽃 을 선택 하여 경 로 를 통 해 연 결 된 모든 화원 의 꽃의 종 류 를 서로 다 르 게 해 야 합 니 다.
선택 한 방안 을 배열 형식 으로 되 돌려 주 는 것 이 답 입 니 다. 그 중에서 answer [i] 는 제 (i + 1) 정원 에서 재배 한 꽃의 종류 입 니 다.꽃의 종 류 는 1, 2, 3, 4 로 표시 한다.답 이 있 을 것 을 보증 하 다.
예시 1:
입력: N = 3, paths = [1, 2], [2, 3], [3, 1] 출력: [1, 2, 3]
예시 2:
입력: N = 4, paths = [1, 2], [3, 4] 출력: [1, 2, 1, 2]
예시 3:
입력: N = 4, paths = [1, 2], [2, 3], [3, 4], [4, 1], [1, 3], [2, 4] 출력: [1, 2, 3, 4]
class Solution {
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        vector<int> G[N];
        for (int i=0; i<paths.size(); i++){//     
            G[paths[i][0]-1].push_back(paths[i][1]-1);
            G[paths[i][1]-1].push_back(paths[i][0]-1);
        }
        vector<int> answer(N,0);//        
        for(int i=0; i<N; i++){
            set<int> color{1,2,3,4};
            for (int j=0; j<G[i].size(); j++){
                color.erase(answer[G[i][j]]);//        
            }
            answer[i]=*(color.begin());//  
        }
        return answer;
    }
};



좋은 웹페이지 즐겨찾기