HackerRank

Bu----- 채용 코딩테스트문제

문제: 주어진 start->end 리스트로 연결된 각 그래프의 노드 수의 루트값의 올림한 값을 더한 결과를 나타내라.

 

from collections import deque
import math

def connectedSum(graph_nodes, graph_from, graph_to):
    graph =[[] for i in range(graph_nodes+1)]
    result=0
    visit=[False]*(graph_nodes+1)
    for i in range(len(graph_from)):
        graph[graph_from[i]].append(graph_to[i])
        graph[graph_to[i]].append(graph_from[i])

    q=deque()

    for i in graph_from:
        cnt=1
        if visit[i]==False:
            visit[i]=True
            q.append(i)
            while q:
                now=q.popleft()
                for j in graph[now]:
                    if visit[j]==False:
                        visit[j]=True
                        cnt+=1
                        q.append(j)
            result+=int(math.ceil(math.sqrt(cnt)))


    cnt=0
    for i in range(1,graph_nodes+1):
        if visit[i]==False:
            cnt+=1

    result+=cnt

    print(result)




graph_nodes=4
graph_from=[1,1]
graph_to=[2,4]

connectedSum(graph_nodes,graph_from,graph_to)