본문 바로가기

알고리즘225

이중 연결 요소(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.
BOJ 1199 - 오일러 회로 https://www.acmicpc.net/problem/1199 양방향그래프 오일러서킷 코드기록용 오일러서킷 존재하면 출력, 없으면 -1출력 오일러트레일은 무시해야 함. ->차수가 홀수인 정점이 없으면 오일러서킷 존재함 int adj[MAX][MAX], n, deg[MAX]; bool odd; vector ans; void euler(int u) { for (int v = 0; v 0) { adj[u][v]--; adj[v][u]--; euler(v); } } ans.push_back(u); } int main() { FAST; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++).. 2020. 2. 13.
WORDCHAIN - 단어제한 끝말잇기 (오일러 경로, 헤밀토니안 경로) https://algospot.com/judge/problem/read/WORDCHAIN 헤밀턴 경로 문제를 오일러경로 문제로 바꾸는 것이 포인트. 모든 정점을 지나는 경로->모든 간선을 지나는 경로 https://suuntree.tistory.com/176코드자세한설명 단어들이 최대 100개 주어질 때, 이 단어들을 단 한번씩만 이용해서 모든 단어들을 사용할 수 있는지 출력. 사용할 수 있다면 그 순서중 아무거나 출력. 모든 단어들을 사용할수 있는지에 대해 그래프를 형성하면, 헤밀토니안 경로를 찾는 문제가 된다.(모든 정점을 정확히 한 번씩 지나는 경로. 외판원 순회(TSP)는 이 경로 중 가장 작은 가중치를 갖는 경로.) 헤밀턴 경로를 찾는 유일한 방법은 조합탐색으로 이 문제의 경우 단어 개수 n!만.. 2020. 2. 12.

티스토리툴바