글 읽기 - 이분탐색 무슨 예제가 틀린거죠??

kkw564 7년 전 0

이분 탐색에서 정의를 이용한것같은데 뭐가 틀린걸까요?

#include <iostream>

using namespace std;

int main()
{
	int tCase;
	int n, m;
	int from, to, flag = 0;
	int arr[20001];

	cin >> tCase;

	while (tCase--)
	{
        // 초기화
		for (int i = 0; i <= 20000; i++)
			arr[i] = -1;

		cin >> n >> m;

        
		for(int i = 0; i < m; i++)
		{
			cin >> from >> to;

		    // 아직 정점이 연결되어있지 않다면
            if(arr[from] == -1)
			{
                // A그룹으로 지정
				arr[from] = 1;
				
                // 만약 for문에서 B그룹이어야 하는데 A 그룹에 있다면 NO
				if (arr[to] == 1)
					flag = 1;
                // 그게 아니라면 B그룹으로 지정
				else
					arr[to] = 0;
			}
            // A그룹에 있지 않고 B그룹에 있다면
			if (arr[from] == 0)
			{
				flag = 1;
			}
            // B그룹에 있지 않고 A그룹에 있다면
			else if (arr[to] == 1)
			{
				flag = 1;
			}
		}
		
        // 위의 조사식에서 한번도 나타나지 않은 노드가 있다면
        // 이분탐색 정의에 오류
		for (int i = 1; i <= n; i++)
			if (arr[i] == -1)
				flag = 1;

	//	cout << arr[1] << " " << arr[2] << " " << arr[3] << " " << arr[4] << endl;
		flag == 1 ? cout << "NO" << endl : cout << "YES" << endl;

		flag = 0;
	}

}

sksdong1 7년 전 1

3 2

3 1

3 2

1 3

2 3

YES

똑같은건데 순서만 바꿔도 답이 달라요

kts1801 7년 전 0

둘다 YES나왔는데 AC받았습니다.

왜 첫번째가 NO가 나오는지 알 수 있을까요??

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

문제

문제

출처

ICPC

이분탐색 무슨 예제가 틀린거죠??

kkw564 7년 전 0

sksdong1 7년 전 1

kts1801 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말