글 읽기 - 1707 질문입니다.. 무엇이 문제인지 모르겠습니다.

reo91004 2년 전 0

BFS로 -1, 1로 색을 구별하고, node_color 배열을 따로 선언해 색깔을 저장하는 방식으로 구현했습니다.

백준에 있는 예제도 맞게 나오고, https://jdselectron.tistory.co... 에 나오는 예제도 정상적으로 출력되는데 백준에서 그냥 '틀렸습니다' 라고 나옵니다. 도저히 해결 방법을 모르겠어서 질문드립니다..

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

//
std::vector<int> graph[20001]; // 1~20000 이용
int node, line;
int node_color[20001];
//
void init() {
    for(int i=1;i<=node;++i) {
        graph[i]=std::vector<int>();
        node_color[i]=0;
    }
}
// 0이면 색x // 1/-1
bool bfs(int cur_node) { //색이 안맞는게 나오면 false return
    std::queue<int> Q;
    Q.push(cur_node);
    node_color[cur_node]=1;
    while(!Q.empty()) {
        cur_node=Q.front();
        Q.pop();

        for(int i=0;i<graph[cur_node].size();++i) {
            if(!node_color[graph[cur_node][i]]&&node_color[cur_node]==1) {
                node_color[graph[cur_node][i]]=-1;
                Q.push(graph[cur_node][i]); // i위치에서 탐색해라
            }
            else if(!node_color[graph[cur_node][i]]&&node_color[cur_node]==-1) {
                node_color[graph[cur_node][i]]=1;
                Q.push(graph[cur_node][i]);
            } // 여기까지 방문하지 않은 노드가 연결되어있을때
            else if(node_color[graph[cur_node][i]]) {
                if(node_color[cur_node]==node_color[graph[cur_node][i]]) {
                    return false;
                }
            }// 방문한 노드가 연결된 경우
        }
    }
    return true;
}

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

    int T;
    std::cin >> T;
    for(int i=0;i<T;++i) {
        std::cin >> node >> line;
        init();
        for(int j=0;j<line;++j) {
            int x,y;
            std::cin >> x >> y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        if(bfs(1)) {
            std::cout << "YES" << '\n';
        }
        else {
            std::cout << "NO" << '\n';
        }
    }

    return 0;
}

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

문제

문제

출처

ICPC

1707 질문입니다.. 무엇이 문제인지 모르겠습니다.

reo91004 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말