글 읽기 - 왜 틀렸는지 모르겠습니다.(코드 주석 있음)

rootsquare 2년 전 0

다음과 같은 논리로 문제를 풀어보았습니다.

이분그래프 판별법: 그래프의 모든 점을 두 가지 색으로 색칠하되, 임의의 이어진 두 정점의 색을 다르게 해서 칠할 수 있으면 이분그래프이다.

풀이 과정(한 테스트 케이스마다):

1. 정점과 간선의 개수를 입력받고, 간선들의 정보를 입력받아 lines와 V(벡터)에 넣는다.

2. 1번 정점부터 n번 정점에 대하여 다음과 같이 진행한다.

2-1. k번째 정점이 색칠되어 있지 않은 경우, 다음을 진행한다.(색칠되어 있으면 이하 단계는 건너뛴다.)

2-2. 2-1의 정점을 색1로 칠한다.

2-3. BFS를 이용하여 현재 점과 연결된 점들을 모두 색칠한다. 색칠할 때는 현재 점과 이어진 점은 색을 다르게 칠한다.(원 점을 색1로 칠했으면 다음 점은 색2를 칠한다.) 만일 BFS를 진행하는 도중 이미 색이 칠해진 점을 만나면 그 방향으로는 더 이상 칠하지 않는다.

3. 색칠된 점들에 대하여, lines에 저장한 간선들을 하나씩 비교해 본다. 만일 모든 간선에 대하여 두 정점의 색이 다르면 YES, 그렇지 않으면 NO이다.

게시판의 반례는 모두 맞게 나오고,

https://www.acmicpc.net/board/... 이 글까지 확인해 보았지만 여전히 틀리고 있습니다.

혹시 반례나 풀이에서 제가 잘못 생각한 부분이 무엇이 있는지 알 수 있을까요?

#include<stdio.h>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
typedef pair<int,int> PP;
queue<PP> Q;
vector<int> V[20010];
int visit[20010];
int lines[200010][3];
int main(void)
{
    int task,vertex,edge,answer;
    int si,gi,ni,ncolor,roll;
    int ti,tcolor;
    scanf("%d",&task);
    for(int k=1; k<=task; k++)
    {//그래프의 이웃한 정점을 같은 색으로 칠하지 않고, 오로지 두 색으로만 칠할 수 있는 그래프를 이분그래프라고 한다.
        answer=1;
        for(int i=1; i<=20001; i++)
        {
            visit[i]=0;
            V[i].clear();
        }
        for(int i=1; i<=200002; i++)
        {
            lines[i][1]=0;
            lines[i][2]=0;
        }
        scanf("%d %d",&vertex,&edge);//정점, 간선 개수.
        for(int i=1; i<=edge; i++)
        {//간선 정보를 입력받는다.
            scanf("%d %d",&si,&gi);
            lines[i][1]=si;
            lines[i][2]=gi;
            V[si].push_back(gi);
            V[gi].push_back(si);
        }
        for(int i=1; i<=vertex; i++)
        {//그래프의 점들을 색칠한다. 색1,색2 이렇게 사용한다. 0은 색이 칠해지지 않았음을 뜻한다.
            if(visit[i]==0)//색칠하지 않은 점인경우
            {
                Q.push(make_pair(i,1));//색 1을 먼저 칠해본다.
                while(!Q.empty())//해당 점과 이어진 점들을 모두 칠한다.(색이 겹치지 않게)
                {
                    ni=Q.front().first;//현재 점
                    ncolor=Q.front().second;//현재 색
                    tcolor=3-ncolor;//다음 색.1이면 2, 2이면 1이 된다.
                    Q.pop();
                    roll=V[ni].size();
                    for(int j=0; j<roll; j++)
                    {//현 정점과 붙어있는 점들은 다른 색으로 칠한다.
                        ti=V[ni][j];
                        if(visit[ti]==0)//아직 색이 칠해지지 않은 점인 경우.
                        {
                            visit[ti]=tcolor;
                            Q.push(make_pair(ti,tcolor));
                        }
                    }
                }
            }
        }
        for(int i=1; i<=edge; i++)
        {
            if(visit[lines[i][1]]==visit[lines[i][2]])
            {//이웃한 두 색이 같은 경우, 이분그래프가 아니다.
                answer=0;
            }
        }
        answer ? printf("YES\n") : printf("NO");//최종 정답을 출력한다.
    }
    return 0;
}

kipa00 2년 전 1

반례입니다.

rootsquare 2년 전 0

NO 다음에 개행문자(\n) 넣는 것을 깜빡하고 있었습니다.

해결했습니다 감사합니다!

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