Module: 심층적으로 검색하십시오. DFS


Problem

5 /12


이분 그래프

Theory Click to read/hide

이분 그래프
 
이분 그래프 - 정점을 두 세트로 나누어 각 에지가 다른 세트의 정점.


종종 이분 그래프의 맥락에서 색상 정점이라는 개념이 사용됩니다. 그래프를 두 부분으로 나누는 것을 꼭짓점에 색상을 두 가지 색상으로 지정합니다. 각 가장자리는 서로 다른 색상의 정점을 연결해야 합니다.

DFS. 
 

알고리즘

우리는 임의의 정점에서 페인팅을 시작하여 임의의 색상으로 페인팅합니다.
각 가장자리를 통과할 때 다음 정점을 반대 색상으로 칠합니다.
인접한 정점을 반복하는 동안 현재 정점과 동일한 색상으로 이미 칠해진 정점을 찾으면 그래프에 홀수 주기가 있는 것입니다. 이는 이분법이 아님을 의미합니다.

Problem

꼭짓점이 두 가지 색상으로 칠해져 같은 색상의 꼭지점을 연결하는 가장자리가 없는 경우(즉, 각 가장자리가 첫 번째 색상의 꼭지점에서 두 번째 꼭지점으로 이동하는 경우) 그래프를 이분 그래프라고 합니다. .
그래프가 주어집니다. 이분인지 확인하고 그렇다면 꼭지점에 색을 지정해야 합니다.
 
입력
첫 번째 줄에는 먼저 숫자 N - 그래프 꼭지점의 수(100을 초과하지 않음)가 포함됩니다. 다음은 0과 1의 NxN 행렬인 인접 행렬입니다(0은 가장자리 없음, 1은 있음을 의미). 그래프는 루프 없이 무방향입니다.
 
출판물 
첫 번째 줄에 YES  또는 NO 메시지 중 하나를 인쇄합니다(그래프가 이분형인지 여부에 따라 다름). 대답이 예인 경우 두 번째 줄에 N개의 숫자를 인쇄합니다. 정점을 색칠할 색상입니다. 첫 번째 색상은 값 1을 사용하고 두 번째 색상 - 값 2. 첫 번째 정점은 색상 1이어야 합니다.
 
예
<헤드> <일># <몸>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

입력 출력
1 <사업부>3 <사업부>0 1 1 <사업부>101
1 1 0
 아니오
2 <사업부>3 <사업부>0 1 1 <사업부>1 0 0 <사업부>1 0 0
예
1 2 2