[백준] 1043번: 거짓말

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

initial

All the test cases showed that at least 1 party had a different length then the rest. So I sorted tha parties based on the length descending and if it contained the banned members, we add all the members of that party to our banned list. It worked for the 6 test cases but when you have something like

6 5
1 6
2 4 5
2 1 2
2 2 3
2 3 4
2 5 6

Where the number of party members (i.e. length of party list) is the same, then my impl logic is limited. My search cannot propagate because all the lengths are the same. So we have to use a different logic - union find.

wrong code:

import sys
input = sys.stdin.readline
per, par = map(int, input().split())
banned = set(list(map(int, input().split()))[1:])
party = []

for _ in range(par):
    tmp = list(map(int, input().split()))
    party.append(tmp[1:])

party.sort(key=lambda x: -len(x))
count = 0
flag=False
for p in party:
    for element in p:
        if element in banned:
            banned.update(i for i in p)
            flag=True
            break
    if flag:
        flag=False
    else:
        count += 1
print(count)

solution

https://velog.io/@dasd412/%EB%B0%B1%EC%A4%80-1043-%EA%B1%B0%EC%A7%93%EB%A7%90-%ED%8C%8C%EC%9D%B4%EC%8D%AC

my find_parent logic was wrong
it should be if par1<par2, parent[par2]=par1. It is node parent[node2]=par1. We are beyond the input child nodes and we are dealing with the parents now so we should assign the parents.

This guy had the same problem as me and I saw his implementation. First we assign each node to itself as a parent but if the nodes are in the banned list, we assign value 0 as their parent. This is important later because later if we find any parent of the party members to be 0, then it means our protagonist cannot lie to the party members. More later

We iterate through each party list and union 2 neighbouring members(union(tmp[i],tmp[i+1]) until list(tmp)-1 to prevent index out of range error. This union will link some parents of nodes to be 0 but it is not done yet cuz we have to union every possible pair before we count any valid cases so we dont place this increment count logic here.

Lastly, we iterate through each party member in the party case and if any of the member’s parent is 0, then we flag it and break (for faster exit). If flag has not been raised, it is a valid case so we increment count. Else we reset the flag.

I saw that guy’s implementation and he places the flag within the party case scope so flag does not have to be reset every party case like when I declared it on global scope.

import sys
input = sys.stdin.readline
per, par = map(int, input().split())
banned = list(map(int, input().split()))[1:]
party = []
parent = [i for i in range(per + 1)]

for ban in banned:
    parent[ban] = 0
def find_parent(node):
    if parent[node] != node:
        parent[node] = find_parent(parent[node])
    return parent[node]

def union(node1, node2):
    par1 = find_parent(node1)
    par2 = find_parent(node2)
    if par1 < par2:
        parent[par2] = par1
    else:
        parent[par1] = par2

for _ in range(par):
    tmp = list(map(int, input().split()))[1:]
    for i in range(len(tmp) - 1):
        union(tmp[i], tmp[i + 1])
    party.append(tmp)

count = 0
flag = False

for p in party:
    for element in p:
        if find_parent(element) == 0:
            flag = True
            break

    if not flag:
        count += 1
    else:
        flag = False

print(count)

complexity

union find is log n and since we are doing it for m times it is m log n. Initialising parent list times n time so total time is n+ m log n.

space is just n cuz we store n number of peeps.

1. Initialization of parent list: O(N)

   • This step initializes the parent list, which has a length of N + 1.

2. Union operations in the loop: O(M * log(N))

   • For each party (M parties), there are at most N - 1 union operations performed. The union operation has a time complexity of log(N).

Therefore, the total time complexity is O(N + M * log(N)).

I hope this clarifies the breakdown of time complexity in the given code.