글 읽기 - 반례를 못찾겠습니다.

glanceyes 4년 전 0

dfs를 스택으로 구현하면서 논리적으로 구현하는데 오류가 생긴 것 같습니다.

아무리 찾아도 반례를 찾지 못하겠네요 ㅠㅠ

혹시 반례 알려주시면 감사하겠습니다.

#include <cstdio>
#include <vector>
#include <stack>
#include <string.h>

using namespace std;

int check[20001];
vector<int> edge[20001];

void dfs(int v) {
    if (check[v] == 0) {
        stack<pair<int, int>> s;
        check[v] = 1;
        s.push(make_pair(v, 0));
        while (!s.empty()) {
            int x, start;
            x = s.top().first;
            start = s.top().second;
            s.pop();
            for (unsigned int i = start; i < edge[x].size(); i++) {
                int y = edge[x][i];
                if (check[y] == 0) {
                    check[y] = check[x] * -1;
                    s.push(make_pair(x, start + 1));
                    s.push(make_pair(y, 0));
                    break;
                }
            }
        }
    }
    return;
}

int bipartite(int v) {
    for (int i = 1; i <= v; i++) {
        dfs(i);
    }
    for (int i = 1; i <= v; i++) {
        for (unsigned int j = 0; j < edge[i].size(); j++) {
            int temp = edge[i][j];
            if (check[i] == check[temp]) {
                return 0;
            }
        }
    }
    return 1;
}

int main() {
    int k, v, e;

    scanf("%d", &k);

    while (k--) {
        scanf("%d %d", &v, &e);

        for (int i = 0; i < v; i++) {
            edge[i].clear();
        }

        memset(check, 0, sizeof(check));

        for (int i = 0; i < e; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            edge[x].push_back(y);
            edge[y].push_back(x);
        }
        
        switch (bipartite(v)) {
        case 0:
            printf("NO\n");
            break;
        case 1:
            printf("YES\n");
            break;
        default:
            break;
        }
    }


    return 0;
}

djm03178 4년 전 1

정점의 번호는 1부터 v까지인데 58번째 줄에서는 0부터 v-1까지를 초기화하고 있습니다.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

glanceyes 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말