글 읽기 - 왜 마지막 정점을 sort해야 정답 처리가 되는지 모르겠습니다.

werq20003 1년 전 0

분명 문제의 입력 조건이 (1 ≤ u < v ≤ N, u ≠ v) 이기 때문에

마지막 정점은 굳이 sort가 필요 없지 않나요?

그래서

에서는 마지막 정점을 sort하지 않아도 통과가 됐는데 이 문제에서는 오답처리를 하네요.

###################################################################### 오답 처리 코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int check[100001];

int output[100001];
int output_cnt;

int N, M, R;

vector<int> v[100001];

void DFS(int n){


        if(check[n] & 1){
                return;
        }

        check[n] = 1;
        output[n] = ++output_cnt;

        for(register int i = 0; i < v[n].size(); i++){
                DFS(v[n][i]);
        }

        return;


}

int main(){


        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        cin >> N >> M >> R;

        int temp_1, temp_2;

        for(register int i = 0; i < M; i++){
                cin >> temp_1 >> temp_2;
                v[temp_1].push_back(temp_2);
                v[temp_2].push_back(temp_1);
        }

        for(register int i = 1; i < N; i++){
                sort(v[i].begin(), v[i].end(), greater<int>());
        }

        DFS(R);

        for(register int i = 1; i <= N; i++){
                cout << output[i] << '\n';
        }

        return 0;

}

############################################################################# 정답 처리 코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int check[100001];

int output[100001];
int output_cnt;

int N, M, R;



vector<int> v[100001];

void DFS(int n){


        if(check[n] & 1){
                return;
        }

        check[n] = 1;
        output[n] = ++output_cnt;

        for(register int i = 0; i < v[n].size(); i++){
                DFS(v[n][i]);
        }

        return;


}

int main(){


        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        cin >> N >> M >> R;

        int temp_1, temp_2;

        for(register int i = 0; i < M; i++){
                cin >> temp_1 >> temp_2;
                v[temp_1].push_back(temp_2);
                v[temp_2].push_back(temp_1);
        }

        for(register int i = 1; i <= N; i++){
                sort(v[i].begin(), v[i].end(), greater<int>());
        }

        DFS(R);

        for(register int i = 1; i <= N; i++){
                cout << output[i] << '\n';
        }

        return 0;

}

wider93 1년 전 0

틀렸던/맞았던 소스코드를 그대로 올려주세요. 현재 코드는 동작하지 않을 것 같습니다.

werq20003 1년 전 0

수정했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 마지막 정점을 sort해야 정답 처리가 되는지 모르겠습니다.

werq20003 1년 전 0

wider93 1년 전 0

werq20003 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말