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

jjh4698 8년 전 0

이분그래프를 dfs로 구현을 해봤는데요

먼저 루트노드 1을 기준으로 인접리스트로 입력을 받았습니다.

예제에 나와있는데로 입력받으면

1 2

2 3

3 4

4 2 이렇게 단방향으로만 인접리스트 벡터에 넣어주고

dfs를 돌리면

1인 루트노드는 색깔 1을 기준으로 자신과 연결된 정점을 3-1 의 색깔로 칠하면서 재귀하게 하였습니다.

그리고 최종적으로 모든 노드를 방문했다고 가정했을때, 각 행 과 연결된 열 노드들의 색깔이 같은것이 있다면

이것은 이분그래프가 아니고, 없다면 이분그래프로 판별하게 하였습니다.

근데 위에서 처럼 단방향으로 제출을했을때는 틀렸습니다가 나오고

양방향으로 넣어줬을때 v[x].push_back(y); v[y].push_back(x) 는 맞았습니다가 나오는 이유가 무엇일까요??

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <stdio.h>
#include <vector>
using namespace std;
 
bool check[20001];
int color[20001];
vector<vector<int> > v;
 
bool dfs(int x, int c)   //color = 1 빨강 2 녹색 
{
    if (check[x] == true)
    {
        color[x] != c;
        return false;
    }
    check[x] = true;
    color[x] = c;
     
    for (int i = 0; i < v[x].size(); i++)
    {
        if (check[v[x][i]]==false)
            dfs(v[x][i], 3 - c);
    }
     
    return true;
 
}
 
 
int main() {
    int t_case;
    int V, E;
    int x, y;
    scanf("%d", &t_case);
 
    while (t_case--)
    {
        memset(color, 0, sizeof(color));
        memset(check, 0, sizeof(check));
        int k = 1;
        scanf("%d %d", &V, &E);
        v.clear();
        v.resize(V+1);
        for (int i = 0; i < E; i++)
        {
            scanf("%d %d", &x, &y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        while (1)
        {
            dfs(1, 1);
            for (int i = 1; i <= V; i++)
            {
                if (check[i] == false)
                {
                    dfs(i, 1);
                    continue;
                }
            }
            break;
        }
 
        for (int i = 0; i <= V; i++)
        {
            for (int j = 0; j < v[i].size(); j++)
            {
                if (color[i] == color[v[i][j]])
                {
                    k = 0;
                    break;
                }
            }
        }
        if (k == 0)
            printf("NO\n");
        else
            printf("YES\n");
         
    }
 
}

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

문제

문제

출처

ICPC

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

jjh4698 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말