공부중의 블로그

본인이 테일 노드이거나, 테일 노드를 가리키거나, 테일 노드로 이어지는 노드를 가리키면 good 노드이다.모든 노드가 good이 되기 위한 최소 포인터 변경 횟수는? 아무래도 union_set 문제인 것 같다. 구체적인 구현으로는,본인의 종결점을 찾는다. 그것이 tail이 아니면 그것을 테일로 가리킨다.모든 노드에 대해 수행한다. 물론 visited를 써 가면서 수행하자. 그렇게 하면 O(N) 수행시간을 얻는다..!! DFS >> 횟수가 곧 최소 횟수이다!! vector visited; for(int i = 0 ; i < graph.size() ; i++){if(visited[i]!=false){// not containing node 1, need to move pointerif(!goDFS) coun..

비방향 그래프에서는 최대 V-1 개의 엣지가 가능하다. spanning tree이다. 그 이상 연결하면 반드시 사이클이 생긴다.방향 그래프에서는 Topological sort를 고려한다고 생각해 보면 맨 앞에서는 V-1개 , V-2 ... 1 의 총합은 V(V-1)/2 개이다.

각 점에서의 최대 트래픽을 구해보자. ex) 1 2 54 3 의 경우 1 142 133 124 115 4가 나와야 한다. 모든 점에서 nearby 점의 값들 중 최대값을 고려하는 듯 한데 이걸 preprocessing으로 풀어서 O(N) 을 만든 것으로 보인다. 그냥 나이브하게 구하면 O(N^2) 알골이 된다. // preprocess your input graph to the following structure // node -> hash set of neighbors // hash set to enable amortized O(1) deletions vector topology(n); vector metadata(n); // contains the population count vector curre..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127#include "stdafx.h"#include #include #include #include #include #include #include #include using namespace std; void makeBFS(..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122#include "stdafx.h"#include #include #include #include #include #include using namespace std; void DFS(vector & graph, vector &visited, int ..

123456789101112131415161718192021222324252627282930313233343536bool findpath(vector & board) { // make graph vector graph(board.size()*board[0].size(), vector()); int count = 0; for (int i = 0; i

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748void IDFS(vector & graph, vector & visited, stack & res, int target) { visited[target] = true; for (int i = 0; i