본문 바로가기

Programming Problems/Graph

셋 전부 합치기 Q 본인이 테일 노드이거나, 테일 노드를 가리키거나, 테일 노드로 이어지는 노드를 가리키면 good 노드이다.모든 노드가 good이 되기 위한 최소 포인터 변경 횟수는?아무래도 union_set 문제인 것 같다. 구체적인 구현으로는,본인의 종결점을 찾는다. 그것이 tail이 아니면 그것을 테일로 가리킨다.모든 노드에 대해 수행한다. 물론 visited를 써 가면서 수행하자. 그렇게 하면 O(N) 수행시간을 얻는다..!! DFS>> 횟수가 곧 ..
N개의 노드에 대해 acyclic이 되는 최대 엣지의 갯수는(방향,비방향) 비방향 그래프에서는 최대 V-1 개의 엣지가 가능하다. spanning tree이다. 그 이상 연결하면 반드시 사이클이 생긴다.방향 그래프에서는 Topological sort를 고려한다고 생각해 보면 맨 앞에서는 V-1개 , V-2 ... 1 의 총합은 V(V-1)/2 개이다.
사이클 없는 그래프에서 각 점에의 최대 트래픽 찾기 Q 각 점에서의 최대 트래픽을 구해보자.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 struct..
배열 스왑해서 정렬하기 (BFS 응용) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201..
끝말잇기 문제 (오일러 경로) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201..
DFS로 보드 길 찾기(그래프 변환) 123456789101112131415161718192021222324252627282930313233343536bool findpath(vector<vector<int>> & board) {    // make graph    vector<vector<int>> gr..
DAG topological sort 응용문제 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748void IDFS(vector<vector<int>> & graph, vector<bool> & visited, stack<int> & res, ..