알고리즘/종만북19 이중 연결 요소(BCC), 단절점, 단절선 SCC와 다르게 무향그래프에서 사용되는 개념 ㅁ BCC 어떤 BCC안에 속한 정점 하나와 그 정점에 인접한 간선들을 지웠을 때, 그 BCC 내에 남은 정점들은 모두 연결됨. (SCC와 유사, 하지만 간선끼리 묶어서 분류) 한번의 dfs로 BCC를 분류할 수 있다. int n, m, vst[MAX], counter; vector g[MAX]; vector bcc; //P는 간선 표현 stack s; int makeBCC(int u, int p) { int ret = vst[u] = counter++; for (int v : g[u]) if (v != p) { //아직 방문하지 않은 간선인 경우 스택에 u-v간선 넣음 if (vst[u] > vst[v]) s.push({ u,v }); //트리간선 if (v.. 2020. 2. 13. DFS트리에서 간선의 종류, 사이클 검출 ㅁ방향그래프 dfs를 수행하면 그래프의 모든 간선을 한 번씩은 만나게 된다. 그래프에서 어떤 점에서 dfs를 수행하면 트리가 만들어지는데, 트리를 중심으로 그래프의 모든 간선의 종류를 구분해보면 1. 트리간선 dfs트리를 이루는 간선 2. 순방향 간선 스패닝 트리의 선조에서 자손으로 연결되지만 트리간선이 아닌 간선 3. 역방향 간선 트리의 자손에서 선조로 연결되는 간선. 당연히 트리간선에 포함 안됨. 그래프의 사이클유무 판단할때 사용하는 간선. ( 이 간선이 존재하면 그래프에 사이클 존재 ) 4. 교차간선 그 외의 모든 간선. 선조-자손관계가 아닌 정점들 간 연결된 간선. vector adj[MAX]; int vst[MAX]; //방문순서 기록. -1이면 방문안된것. bool fin[MAX]; int c.. 2020. 2. 13. WORDCHAIN - 단어제한 끝말잇기 (오일러 경로, 헤밀토니안 경로) https://algospot.com/judge/problem/read/WORDCHAIN 헤밀턴 경로 문제를 오일러경로 문제로 바꾸는 것이 포인트. 모든 정점을 지나는 경로->모든 간선을 지나는 경로 https://suuntree.tistory.com/176코드자세한설명 단어들이 최대 100개 주어질 때, 이 단어들을 단 한번씩만 이용해서 모든 단어들을 사용할 수 있는지 출력. 사용할 수 있다면 그 순서중 아무거나 출력. 모든 단어들을 사용할수 있는지에 대해 그래프를 형성하면, 헤밀토니안 경로를 찾는 문제가 된다.(모든 정점을 정확히 한 번씩 지나는 경로. 외판원 순회(TSP)는 이 경로 중 가장 작은 가중치를 갖는 경로.) 헤밀턴 경로를 찾는 유일한 방법은 조합탐색으로 이 문제의 경우 단어 개수 n!만.. 2020. 2. 12. 오일러 경로 '한붓그리기' 로 모든 간선을 칠한다면 그게 바로 오일러 경로 오일러 경로가 존재하려면 1. 출발점=도착점인 경우 (오일러 서킷) 양방향: 모든 정점의 차수가 짝수면 된다. 단방향: 모든 정점의 indegree==outdegree 2. 출발점 != 도착점인 경우 (오일러 트레일) 양방향: 출발점과 도착점의 차수는 홀수고 나머지 정점의 차수는 짝수면 된다. 단방향: outdegree[i]==indegree[i]+1인 점(시작점) 단 한개, indegree[i]==outdegree[i]+1인 점(도착점) 단 한개 존재. 컴포넌트가 여러 개인 경우 당연히 오일러 서킷이 존재하지 않을 거라고 생각할 수 있지만, 컴포넌트의 정점이 하나인 경우 간선이 존재하지 않는다는 점을 유념해야 한다. -> 모든 간선이 하나의.. 2020. 2. 12. 이전 1 2 3 4 5 다음
