BOJ 23255

백준 23255, Graph

CPP STL 기능들을 까먹어서 풀이를 바로 생각 하고도 구현을 못해서 정답을 봤다.
솔직히 아직도 WA가 왜 WA가 뜨는지 모르겠다.(맞왜틀?)
아마 구현을 못해서 MLE/RTE 가 WA로 찍히거나, 디버깅도 못 할 정도로 못 짠거 같다.
출제진의 원본 정해가 깔끔하다. 또한 친절하게도
std::vector<> , unique() 의 조합과 std::set()의 사용을 같이 알려준다.
정해링크

Source Code

23255링크

// https://www.acmicpc.net/problem/23255

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <vector>

#define ll long long

#define pii pair<int, int>
#define pll pair<ll, ll>
#define MAXI 1000000000
#define cplx complex<double>
#define MOD 9901
const double PI = acos(-1);
const ll INF = INT_MAX / 4;

using namespace std;

int N, M;
vector<vector<int>> adjlist(100100);
int max_degree = 0;
bool visited[100100];
set<int> pallete;
int color[100100];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    // adjlist.resize(N+1);
    for (int i = 0; i < M; ++i) {
        int s, e;
        cin >> s >> e;
        adjlist[s].push_back(e);
        adjlist[e].push_back(s);
    }

    max_degree = -1;
    for (int i = 1; i <= N; ++i) {
        max_degree = max<int>(max_degree, (adjlist[i].size()));
        sort(adjlist[i].begin(), adjlist[i].end());
    }

    memset(visited, 0, sizeof(visited));
    memset(color, 0, sizeof(color));

    for (int i = 1; i <= N; ++i) {
        pallete.clear();
        visited[i] = true;
        color[i] = 1;

        for (int j = 0; j < adjlist[i].size(); ++j) {
            if (visited[adjlist[i][j]]) pallete.insert(color[adjlist[i][j]]);
        }
        for (auto j : pallete) {
            if (j != color[i])
                break;
            else
                ++color[i];
        }
    }

    for (int i = 1; i <= N; ++i) {
        printf("%d ", color[i]);
    }

    return 0;
}

/*

//amsminn's solution using vector + unique


#include <bits/stdc++.h>
using namespace std;

vector<int> gh[101010];
int color[101010];

int main() {
    int n, m, a, b;
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d", &a, &b);
        gh[a].push_back(b);
        gh[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        vector<int> near;
        for (int j : gh[i]) {
            if (color[j] != 0)
                near.push_back(color[j]);
        }
        sort(near.begin(), near.end());
        near.erase(unique(near.begin(), near.end()), near.end());
        color[i] = 1;
        for (int j : near) {
            if (j != color[i])
                break;
            color[i]++;
        }
        printf("%d ", color[i]);
    }
}

//WA

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <vector>

#define ll long long

#define pii pair<int, int>
#define pll pair<ll, ll>
#define MAXI 1000000000
#define cplx complex<double>
#define MOD 9901
const double PI = acos(-1);
const ll INF = INT_MAX / 4;

using namespace std;

int N, M;
vector<vector<int>> adjlist(100100);
int max_degree = 0;
bool visited[100100];
bool pallete[100100];
int color[100100];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    //adjlist.resize(N+1);
    for (int i = 0; i < M;++i){
        int s, e;
        cin >> s >> e;
        adjlist[s].push_back(e);
        adjlist[e].push_back(s);
    }

    max_degree = -1;
    for (int i = 1; i <= N;++i){
        max_degree = max<int>(max_degree, (adjlist[i].size()));
        sort(adjlist[i].begin(), adjlist[i].end());
    }

    memset(visited, 0, sizeof(visited));
    memset(color, 0, sizeof(color));

    visited[1] = true;
    color[1] = 1;


    memset(pallete, 0, sizeof(pallete));

    for (int i = 2; i <= N;++i){
        if(adjlist[i].size() == 0){
            visited[i] = 1;
            color[i] = 1;
            continue;
        }
        else{
            memset(pallete, 0, sizeof(pallete));
            visited[i] = true;
            int col = -1;

            for (int j = 0; j < adjlist[i].size(); ++j) {
                if (visited[adjlist[i][j]]) pallete[adjlist[i][j]] = true;
            }
            for (int j = 1; j <= N; ++j) {
                if (!pallete[j]) {
                    color[i] = j;
                    break;
                }
            }
        }
    }

    for (int i = 1; i <= N;++i){
        printf("%d ", color[i]);
    }

    return 0;
}

*/

PREVIOUSBOJ 14488

NEXTDaily Dose of Paper : Sparse Continual Learning on the Edge