A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees.
The employees are numbered from 0 to n - 1. Each employee has a favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself.
Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return the maximum number of employees that can be invited to the meeting.
Example 1:
Input: favorite = [2,2,1,2]
Output: 3
Explanation:
The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table.
All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously.
Note that the company can also invite employees 1, 2, and 3, and give them their desired seats.
The maximum number of employees that can be invited to the meeting is 3.
Example 2:
Input: favorite = [1,2,0]
Output: 3
Explanation:
Each employee is the favorite person of at least one other employee, and the only way the company can invite them is if they invite every employee.
The seating arrangement will be the same as that in the figure given in example 1:
- Employee 0 will sit between employees 2 and 1.
- Employee 1 will sit between employees 0 and 2.
- Employee 2 will sit between employees 1 and 0.
The maximum number of employees that can be invited to the meeting is 3.
Example 3:
Input: favorite = [3,0,1,4,1]
Output: 4
Explanation:
The above figure shows how the company will invite employees 0, 1, 3, and 4, and seat them at the round table.
Employee 2 cannot be invited because the two spots next to their favorite employee 1 are taken.
So the company leaves them out of the meeting.
The maximum number of employees that can be invited to the meeting is 4.
Constraints:
- n == favorite.length
- 2 <= n <= 105
- 0 <= favorite[i] <= n - 1
- favorite[i] != i
뭐... graph 문제 중에 엄청 어려운 축에 속하는 문제라고 한다.
확 한 번 몰입해봤다가 풀어보자.
1. Python
기본 test case는 통과했는데,
모든 edge case를 통과하진 못했다.
뭔가 투박했던 나의 첫 번째 solution
class Solution:
def maximumInvitations(self, favorite: List[int]) -> int:
ans = 0
m = {}
n = len(favorite)
for idx, val in enumerate(favorite):
m[idx] = val
for i in range(n):
visited = [i]
val = favorite[i]
while val not in visited :
visited.append(val)
val = m[val]
# 중간에 visited 에서 cycle이 발생한 경우
# 1, make a cycle from i
if i == val : ans = max(ans,len(visited))
# 2, make a cycle not from i and no 2-component cycle
elif val != visited[-2] : ans = max(ans,len(visited)-visited.index(val))
# 3, make a cycle not from i and 2-component cycle
else : ans = max(ans,len(visited))
return ans
제대로 된 풀이는 아래와 같다..
class Solution:
def maximumInvitations(self, favorite: List[int]) -> int:
adj=defaultdict(list)
transpose=defaultdict(list)
#first we apply kosaraju, its a cycle, it is that answer itself
#or we can combine multiple 2 sized connected components (if 0's fav is 1 and 1s fav is 0) ->one exception case to consider
#max of both the above conditions
for i in range(len(favorite)):
adj[i].append(favorite[i])
transpose[favorite[i]].append(i)
stack=[]
visited=[False]*len(favorite)
def dfs(node):
visited[node]=True
for n in adj[node]:
if not visited[n]:
dfs(n)
stack.append(node)
for i in range(len(favorite)):
if not visited[i]:
dfs(i)
sccs=[] #list of sets of each scc
scc=set()
visited=[False]*len(favorite)
def traverseForScc(node):
visited[node]=True
scc.add(node)
for n in transpose[node]:
if not visited[n]:
traverseForScc(n)
while stack:
top = stack.pop()
if not visited[top]:
scc = set()
traverseForScc(top)
sccs.append(scc)
ans=max([len(scc) if len(scc)!=2 else -1 for scc in sccs])
#above was from kosaraju
def findLongestArm(a,b):
l=0
for node in transpose[a]:
if node!=b:
l=max(l,1+findLongestArm(node,b))
return l
twoNodeSccs = 0
for n1,n2 in [scc for scc in sccs if len(scc)==2]:
twoNodeSccs+= 2 + findLongestArm(n1,n2) + findLongestArm(n2,n1)
return max(ans,twoNodeSccs)
위 문제를 topological sort로 풀면 아래와 같다.
from collections import deque, defaultdict
class Solution:
def maximumInvitations(self, favorite: List[int]) -> int:
n = len(favorite)
in_degree = [0] * n # 각 노드의 진입 차수
graph = defaultdict(list) # 그래프 표현
tail_length = [0] * n # 각 노드의 꼬리 길이 저장
# 그래프와 진입 차수 초기화
for i in range(n):
graph[favorite[i]].append(i)
in_degree[favorite[i]] += 1
# 위상 정렬을 위한 큐 초기화
queue = deque()
for i in range(n):
if in_degree[i] == 0:
queue.append(i)
# 위상 정렬로 꼬리 길이 계산
while queue:
node = queue.popleft()
next_node = favorite[node]
tail_length[next_node] = max(tail_length[next_node], tail_length[node] + 1)
in_degree[next_node] -= 1
if in_degree[next_node] == 0:
queue.append(next_node)
# 사이클 길이 계산
visited = [False] * n
max_cycle_length = 0
for i in range(n):
if in_degree[i] > 0 and not visited[i]: # 사이클에 속한 노드
cycle_length = 0
current = i
while not visited[current]:
visited[current] = True
cycle_length += 1
current = favorite[current]
max_cycle_length = max(max_cycle_length, cycle_length)
# 2-Component Cycle 처리
two_component_max = 0
for i in range(n):
if favorite[favorite[i]] == i and i < favorite[i]: # 서로를 좋아하는 두 노드
two_component_max += tail_length[i] + tail_length[favorite[i]] + 2
# 최대값 반환
return max(max_cycle_length, two_component_max)