종만북10 오일러 경로 '한붓그리기' 로 모든 간선을 칠한다면 그게 바로 오일러 경로 오일러 경로가 존재하려면 1. 출발점=도착점인 경우 (오일러 서킷) 양방향: 모든 정점의 차수가 짝수면 된다. 단방향: 모든 정점의 indegree==outdegree 2. 출발점 != 도착점인 경우 (오일러 트레일) 양방향: 출발점과 도착점의 차수는 홀수고 나머지 정점의 차수는 짝수면 된다. 단방향: outdegree[i]==indegree[i]+1인 점(시작점) 단 한개, indegree[i]==outdegree[i]+1인 점(도착점) 단 한개 존재. 컴포넌트가 여러 개인 경우 당연히 오일러 서킷이 존재하지 않을 거라고 생각할 수 있지만, 컴포넌트의 정점이 하나인 경우 간선이 존재하지 않는다는 점을 유념해야 한다. -> 모든 간선이 하나의.. 2020. 2. 12. DICTIONARY - 고대어 사전 (위상정렬) https://algospot.com/judge/problem/read/DICTIONARY 위상정렬 기본예제. dfs로 위상정렬 순서 정해주는 것 기록용 알파벳의 순서를 그래프로 표현하여 사이클이 있다면 INVALID 출력, 없다면 위상정렬된 순서로 출력 생략. dfs부분 유념 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); using namespace std; typedef lon.. 2020. 2. 12. FORTRESS - 요새 (트리) https://algospot.com/judge/problem/read/FORTRESS 트리의 지름을 구하는 문제. 임의의 한 점에서 가장 먼 점u, u에서 가장 먼 점v에 대해 u~v거리구하면된다. 서로가 서로에게 포함되거나 포함하는 원들이 최대 100개 주어진다.(겹치거나 접하는 경우 없음) 이때 임의의 두 점 사이에 건너야 하는 벽의 최대 개수를 구해라. 큰 원u가 작은원 v를 포함하는 것을 u->v라 할때 전체 형태는 트리의 형태가 된다. 간선을 이어줄때, 예를들어 a->b->c 인 경우 a->c를 잇지 않도록 주의한다. 반지름을 기준으로 오름차순 정렬하여 적절히 처리해주면 된다. 그리고 트리의 지름을 구하면 된다. 간선을 이어주는 부분 for (int i = 0,x,y,r; i < n; i++).. 2020. 2. 8. 트리 struct treeNode { int element; treeNode * parent; vector children; } * 이진 트리: 자식을 최대 두 개 갖는 트리 * 이진 탐색 트리: 이진트리. 어떤 노드에서 left엔 자기보다 작은 값, right엔 자기보다 큰 값을 유지하는 식 * 힙: 포화 이진트리. 노드가 들어갈 수 있는 자리가 비어있는 경우가 없으므로 일반적으로 배열로 구현. * 구간트리: * 상호 배타적 집합 구조(disjoint set) : 각 노드는 부모를 가리키는 포인터는 있지만 자식에 대한 정보는 없다. 2020. 2. 8. 이전 1 2 3 다음