Funcia
Lv.42-satbinary-searchgraphscc

처음으로 모순이 생기는 요청

메모리 제한
256 MB
정확성 시간 제한
20000 ms
푼 사람
0
0

스위치 n개가 있고 각 스위치는 켜짐(true) 또는 꺼짐(false) 중 하나입니다. 스위치 번호는 1부터 n까지입니다.

요청이 clauses 순서대로 하나씩 들어옵니다. 요청 clauses[i] = [x, y]는 "x 또는 y 중 적어도 하나는 지켜 달라"는 뜻입니다. 각 수는 다음과 같이 읽습니다.

  • 양수 v — "v번 스위치가 켜져 있어야 한다"
  • 음수 -v — "v번 스위치가 꺼져 있어야 한다"

x와 y가 같은 스위치를 가리킬 수도 있습니다. 예를 들어 [3, 3]은 "3번은 반드시 켜짐", [2, -2]는 항상 지켜지는 요청입니다.

요청을 앞에서부터 받아들이다 보면, 어느 순간 지금까지의 요청을 모두 만족하는 스위치 상태가 존재하지 않게 될 수 있습니다. 그렇게 만드는 첫 요청의 인덱스(0부터)를 반환하세요. 모든 요청을 동시에 만족할 수 있으면 -1을 반환합니다.

입출력 예

nclausesresult
3[[1, 2], [-1, 3], [-2, -3], [-3, 1]]-1
2[[1, 1], [-1, 2], [-2, -1], [2, 2]]2
2[[1, 2], [-1, 2], [1, -2], [-1, -2]]3

입출력 예 설명

예 1 — 1번 켜짐, 2번 꺼짐, 3번 켜짐이면 네 요청이 모두 지켜집니다.

예 2 — 요청 0은 1번을 켜게 하고, 요청 1("1번 꺼짐 또는 2번 켜짐")은 2번을 켜게 합니다. 요청 2("2번 꺼짐 또는 1번 꺼짐")는 이제 지킬 수 없으므로 답은 2입니다.

예 3 — 처음 세 요청은 두 스위치를 모두 켜면 지켜지지만, 네 요청을 합치면 두 스위치의 어떤 조합도 통하지 않습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(n: int, clauses: int[][]) → int

제한 사항

  • 1≤1 \le n ≤50,000\le 50{,}000
  • 1≤M=1 \le M = clauses.length ≤100,000\le 100{,}000
  • clauses[i] = [x, y], 1≤∣x∣,∣y∣≤1 \le |x|, |y| \le n (0은 나오지 않습니다)

기대 복잡도

시간
O((N + M) log M)
공간
O(N + M)

입출력 예

nclauses기대 출력
3[[1,2],[-1,3],[-2,-3],[-3,1]]-1
2[[1,1],[-1,2],[-2,-1],[2,2]]2
2[[1,2],[-1,2],[1,-2],[-1,-2]]3

힌트

힌트

1. 한 번의 판정 — 2-SAT

요청 "a 또는 b"는 두 개의 함의와 같습니다: "a가 거짓이면 b", "b가 거짓이면 a". 리터럴(스위치 v의 켜짐/꺼짐) 2n2n개를 정점으로, 함의를 간선으로 하는 함의 그래프를 만듭니다.

어떤 스위치의 "켜짐"과 "꺼짐"이 **같은 강한 연결 요소(SCC)**에 있으면 서로를 강제하므로 모순이고, 그런 스위치가 없으면 반드시 해가 존재합니다. 타잔/코사라주 알고리즘으로 O(n+M)O(n + M)에 판정합니다.

2. 첫 모순 위치 — 이분 탐색

요청을 추가하면 조건이 늘어날 뿐이므로, "앞의 k개를 만족할 수 있는가"는 k에 대해 단조입니다(한 번 불가능해지면 계속 불가능). 따라서 가능한 마지막 k를 이분 탐색하면 판정을 O(log⁡M)O(\log M)번만 하면 됩니다.

복잡도 목표

O((n+M)log⁡M)O((n + M) \log M)입니다. 요청을 하나 받을 때마다 다시 판정하는 O(M(n+M))O(M(n + M)) 풀이는 효율성 테스트에서 시간 초과가 납니다. 재귀 DFS는 깊이가 10510^5까지 갈 수 있으니 언어에 따라 반복문으로 구현하세요.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)364 ms추정
C++ (GCC, gnu++23)364 ms도출됨
Python 3.136948 ms도출됨
Java 252034 ms도출됨
Kotlin 2.4 (JVM)1728 ms추정
C# 14 (.NET 10)1728 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.