글 읽기 - 반례?

gshs340507 5년 전 0

66%에서 틀렸다고 뜨는데 반례가 있는지 궁금합니다.

또한 isBG 함수에서 그래프를 함수 인자로 전달할 때 vector <int> (*G)로 전달하면 reference로 전달되는게 맞나요?

#include <iostream>
#include <vector>
#define MAX 20010

using namespace std;

void ans();
bool isBG(vector <int> (*G), vector <int>& color, int here);

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int Tnum;
    cin >> Tnum;
    while(Tnum--){
        ans();
    }
}

void ans()
{
    vector <int> graph[MAX];
    int V, E;
    cin >> V >> E;
    vector <int> color(V + 1, 0);
    for(int i = 0; i < E; i++){
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);    
    }
    color[1] = 1;
    bool isThatBG = true;
    for(int i = 1; i <= V; i++){
        isThatBG = isThatBG && isBG(graph, color, i);   
    }
    if(isThatBG) cout << "YES" << '\n';
    else cout << "NO" << '\n';
}

bool isBG(vector <int> (*G), vector <int>& color, int here)
{
    bool ret = true;
    for(int i = 0; i < G[here].size(); i++){
        int there = G[here][i];
        if(color[there] == color[here]) return false;
        if(color[there] != 0) continue;
        color[there] = color[here] == 1 ? 2 : 1;
        ret = (ret && isBG(G, color, there)); 
    }
    return ret;
}

gshs340507 5년 전 0

제가 제 질문에 답을 올리네요//

DFS를 하기 전에 1번 정점만 색을 설정해 줘서 틀린 거고, DFS 시작점들은 색이 설정되지 않았다면 먼저 설정해 줘야 합니다. 그러면 풀릴거에요....

bool isThatBG = true;

for(int i = 1; i <= V; i++){

if(color[i] == 0) color[i] = 1;

isThatBG = isThatBG && isBG(graph, color, i);

}

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

문제

문제

출처

ICPC

반례?

gshs340507 5년 전 0

gshs340507 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말