글 읽기 - 이분 그래프 질문입니다.

mhkim4886 5년 전 1

일단, 풀이 자체는 간선을 보면서 색깔을 정해줍니다. 28%에서 WA를 받고, 이렇게 하면 기본적으로 안 된다는 건 알고 있는데..

그렇다면 왜 DFS로 풀면 맞는지
간선을 정렬해 주어도 안 되는지 (왜 안 되는지...)

가 궁금합니다. DFS로 푸는 것과, 간선 보면서 색깔 정하는 것 모두 결국은 간선을 다 보는 거고 순서가 중요한 거 같은데 왜 하나는 되고 하나는 안 되는지가 궁금하네요.

감사합니다.

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tgmath.h>
#include <tuple>
#include <unistd.h>
#include <unordered_map>
#include <vector>
using namespace std;

typedef long long int lli;
typedef pair<int, int> pii;
typedef pair<lli, lli> plli;
typedef unsigned char byte;
typedef unsigned int uint;
typedef unsigned long long int ulli;

int check[21000];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    scanf("%d", &n);

    for (int t = 1; t <= n; t++)
    {
        set<int> a, b;
        vector<pii> edges;
        int v, e;
        scanf("%d %d", &v, &e);
        for (int i = 1; i <= v; i++)
            check[i] = 0;
        for (int i = 0; i < e; i++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            pii p = minmax({x, y});
            edges.push_back(p);
        }
        sort(edges.begin(), edges.end());
        check[1] = 1;
        for (int i = 0; i < e; i++)
        {
            int x = edges[i].first, y = edges[i].second;
            if (check[x] == 0 && check[y] == 0)
            {
                check[x] = 1;
                check[y] = 2;
            }
            else if (check[x] == check[y])
                goto FAIL;
            else
            {
                if (check[x] == 0)
                    check[x] = check[y] == 1 ? 2 : 1;
                if (check[y] == 0)
                    check[y] = check[x] == 1 ? 2 : 1;
            }
        }
        printf("YES\n");
        continue;
    FAIL:
        printf("NO\n");
    }
}

mhkim4886 5년 전 0

코드 중간의 set<int> a, b는 사용하지 않습니다(지워도 됩니다).

djm03178 5년 전 1

TC 수가 조건에 안 맞긴 하지만 틀린 이유를 설명하기에는 충분한 케이스 하나 드립니다.

1
4 3
1 4
2 3
3 4
정답: YES
출력: NO

mhkim4886 5년 전 0

아 이런 경우가 있군요... 감사합니다! :D

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

문제

문제

출처

ICPC

이분 그래프 질문입니다.

mhkim4886 5년 전 1

mhkim4886 5년 전 0

djm03178 5년 전 1

mhkim4886 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말