백준 1707 이분 그래프

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

뭔 개소린지 모르겠어서 인터넷을 찾아보았다.

 

이분그래프는

​이렇게 빨간색은 빨간색끼리 연걸 x, 검은색은 검은색끼리 연결 x 하는 그래프를 말한다.

 

1. 인접한 두 점이 같은 색깔이라면, 이분그래프가 아니다.

2. 만일 어디에도 연결되지 않은 점이라면, 이는 빨간, 검정 두개다 될 수 있다.

3. 모든 정점이 서로 연결되지 않았어도, 이분그래프이다.

 

이 3가지를 생각한다.

 

dfs든 bfs든 원리는 똑같다.

아직 방문하지 않은 노드를 탐색하면서,  (비연결 그래프인 경우도 고려)

 

방문하지 않았다면, 레벨에 따라 다른색을 칠한다 ex 지금 빨이라면 이 다음레벨은 검, 그다음은 빨 .....

이미 방문한 노드와 연결된다면,  현재노드색==방문한노드색이라면 인접한 정점이 같은색인것이다.

그런경우엔 싹다종료하고 no출력

끝까지했는데 종료조건을 만족못했으면 yes출력

 

#bfs

import sys
input=sys.stdin.readline
from collections import deque

def bfs(node):
    global flag
    s=deque()
    s.append(node)
    visited[node]='white'
    while s:
        tmp=s.popleft()
        color=visited[tmp]
        for i in graph[tmp]:
            if not visited[i]:
                visited[i]=['white','black'][color=='white']
                s.append(i)

            else:
                if color == visited[i]:
                    flag=True
                    return 







for _ in range(int(input())):
    v,e=map(int,input().split())

    graph=[[]for _ in range(v+1)]
    visited=[False for _ in range(v+1)]
    for _ in range(e):
        a,b=map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)

    flag=False
    for i in range(1,v+1):
        if not visited[i]:
            bfs(i)
            if flag:
                
                break
    print('NO' if flag else 'YES')

#dfs

주의할점: 재귀로푸는거니깐 recursionlimit설정안하면 오류난다.

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from collections import deque

def dfs(node,value):
    global flag
    visited[node]=value
    for i in graph[node]:
        if not visited[i]:
            dfs(i,-value)

        else:
            if value==visited[i]:
                flag=True

        if flag:
            return
        
        







for _ in range(int(input())):
    v,e=map(int,input().split())

    graph=[[]for _ in range(v+1)]
    visited=[False for _ in range(v+1)]
    for _ in range(e):
        a,b=map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)

    flag=False
    for i in range(1,v+1):
        if not visited[i]:
            dfs(i,1)
            if flag:
                
                break
    print('NO' if flag else 'YES')