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

dearsanta 6년 전 1

어떤 케이스에서 처리를 못하는지 모르겠습니다.

이분그래프를 판별하는 방법이 잘못되었나요?

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>

using namespace std;
vector<int> a[20001];
int colorCheck[20001];

void bfs(int);

int main()
{

    int k,vc,ec;
    scanf("%d",&k);

    //테스트케이스 수 입력
    for(int i=0;i<k;i++)
    {

        // 벡터 초기화
        for(int j=1;j<=vc;j++)
        {
            a[j].clear();
        }

        //정점 간선 수 입력
        scanf("%d %d",&vc,&ec);

        // 정점 간선 입력
        for(int j=0;j<ec;j++)
        {
            int v,e;
            scanf("%d %d",&v,&e);

            a[v].push_back(e);
            a[e].push_back(v);

        }

        for(int i=1;i<=vc; ++i)
        {
            if(colorCheck[i]==0)
                bfs(i);
        }

        bool isGraph = true;

        for (int i = 1; i <= vc; ++i)
            for (int j = 0; j < a[i].size(); ++j)
            {
                int next = a[i][j];
                if (colorCheck[next] == colorCheck[i])
                    isGraph = false;
            }


        printf("%s\n",isGraph ? "YES" : "NO");

    }


    return 0;
}

void bfs(int start)
{
    queue<int> q;
    colorCheck[start] = 1;
    q.push(start);

    while(!q.empty())
    {
        int node = q.front();
        q.pop();

        for(int i=0; i<a[node].size();i++)
        {
            int next = a[node][i];
            if (colorCheck[next] == 0)
            {
                colorCheck[next] = colorCheck[node] == 1 ? 2 : 1;
                
                q.push(next);
            }
        }
    }
}

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

문제

문제

출처

ICPC

이분그래프 질문있습니다.

dearsanta 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말