본문 바로가기

Programming Problems/Graph

셋 전부 합치기 Q

본인이 테일 노드이거나, 테일 노드를 가리키거나, 테일 노드로 이어지는 노드를 가리키면 good 노드이다.

모든 노드가 good이 되기 위한 최소 포인터 변경 횟수는?


아무래도 union_set 문제인 것 같다. 구체적인 구현으로는,

본인의 종결점을 찾는다. 그것이 tail이 아니면 그것을 테일로 가리킨다.

모든 노드에 대해 수행한다. 물론 visited를 써 가면서 수행하자. 그렇게 하면 O(N) 수행시간을 얻는다..!! DFS


>> 횟수가 곧 최소 횟수이다!!


vector<bool> visited;


for(int i = 0 ; i < graph.size() ; i++){

if(visited[i]!=false){

// not containing node 1, need to move pointer

if(!goDFS) count++;

}

}


return count;



https://www.careercup.com/question?id=5840928073842688