그냥 하는 노트와 메모장

분류 - [ 오일러 회로 ] 도로를 두 개 이상을 가지는 도시는 반드시 두 레스토랑을 갈 수 있어야 한다. 도로가 없거나 하나 이하의 경우는 생각하지 않기 때문에, 이 명제를 좀 변형 시켜보자. "도로를 두 개 이상을 가지는 도시에 대해 두 레스토랑을 보장하기 위해서 A 레스토랑이 있는 도로의 수를 Acnt, B 레스토랑이 있는 도로의 수를 Bcnt라고 할 때, Acnt는 Bcnt와 같아야 한다." 이것이 의미하는 바는 A와 B 레스토랑의 수를 같게 하면 명확하게 문제에서 원하는 도로를 배치할 수 있다. 따라서 A와 B를 진입/ 진출 간선처럼 생각하고, 항상 진입 간선 수=진출 간선 수가 같은 오일러 회로를 이용하여 문제를 해결한다. 단, 여기서 예외처리를 해줘야하는 점이 있다. 우선 Component가..

해당 게시글은 아래 속성에 맞춰 작성되어있습니다 :) * 무향 그래프(양방향 그래프, Undirected graph) * Cut vertex(절단점, 단절점) 절단점이란 이 점과 이어진 모든 간선을 지웠을 때 두 개 이상의 Component로 나뉘어 지는 정점을 말한다. 역방향 간선을 이용하여 DFS 한 번만에 절단점을 찾을 수 있다. DFS를 통해 DFS spanning tree를 구성하면 정점 u는 아래처럼 분류할 수 있다. 1. u가 root다 2. u가 root가 아니다. 1. u가 root다 정점 u가 root인 경우, 자식의 개수에 따라 절단점이 될 수도 있고 아닐 수도 있다. 자식이 없는 경우는 당연하고, 하나인 경우에도 root가 사라진다고 두 개의 Component로 나눠지는 것은 아니기..

* Mike and Fish (http://codeforces.com/contest/547/problem/D) 뭐.. 문제 내용을 보면 생선을 싫어하는 곰, 마이크가 파란 생선과 빨간 생선을 2차원 좌표에 있는 바구니(?)에 하나씩 넣고자 한다. 또한 하나의 x축이나 y축에 대해 파란 생선 개수와 빨간 생선 개수의 차이가 1 이하로 만들기 위해 생선들을 각 좌표에 어떻게 배치시킬 것인지를 묻는 문제다. [분류 - Eulerian circuit/ Euler circult/ 오일러 회로/ 오일러 서킷] b clr[a] += (acc % 2 ? 1 : -1), clr[b] += (acc % 2 ? 1 : -1); x = a % 2 ? b : a; y = a % 2 ? a : b; ans[pool[make_pa..

* 오일러 회로 * 백준 온라인 저지 1. 오일러 회로 (https://www.acmicpc.net/problem/1199) 문제 이름부터가 오일러 회로다.. ㅎㅎ 가장 기본적인 오일러 회로를 따라가면 된다. 또한 무방향 그래프이기 때문에 방향성에 대해 확인할 필요가 없다. 기초적인 오일러 회로가 있는지 확인한 뒤, DFS를 돌리면 된다. 인접 행렬 코드 : #include #include using namespace std; int adj[1000][1000], n; vector c; void eulerianCircuit(int u) { for(int v=0;v= j) continue; addEdge(i, j, cap); } for (i = 0; i < n; i++) f &= (deg[i] && !(d..

* 오일러 서킷 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 시작점으로 돌아오기 때문에 오일러 서킷은 사이클임을 알 수 있다. * 오일러 경로 그래프의 모든 간선을 정확히 한 번씩 지나는 경로를 말한다. 시작점과 도착점이 다를뿐(오일러 경로는 사이클이 아니다), 나머지 속성은 오일러 서킷과 같다. * 오일러 서킷/경로 존재 조건 배제의 방식으로 접근한다. 반대로 오일러 서킷이 존재할 수 없는 그래프를 파악하면 된다. u = v의 경우는 오일러 서킷이고, u != v의 경우는 오일러 경로를 말한다. 1. Graph components가 두 개 이상 Components가 두 개 이상이면 한 번의 연산(사이클)이 절대로 모든 간선을 지날 수 없다. 2-1. (양/무방향 그래..

* 위상 정렬(Topological sort) 의존성이 있는 작업들이 주어질 때, 이들을 어떤 순서로 수행해야 하는지 계산할 때 필요하다. 이런 DAG의 정점을 배열하는 것을 위상 정렬이라 한다. 구현 방식은 두 가지 방식이 있다. DFS와 BFS. 1. DFS BFS와 다르게 indegree 배열이 필요가 없다. 또한 나중엔 반드시 reversing process가 필요하다. 코드 : #include vector visit, order; void dfs(int here){ visit[here] = 1; for(int there = 0; there < adj.size(); ++there) if(adj[here][there] && !visit[there]) dfs(there); order.push_back..

* DSU (Disjoint-Set Union, Union-Find 또는 상호배제 집합) DSU에 관련된 문제 중 푼 문제를 소개합니당 1. Codeforce 1-1. Serial Time! (http://codeforces.com/contest/60/problem/B) 단순히 BFS 돌려도 되지만, DSU로 풀어보고 싶어서 적용해봤다. 인접한 6 이웃에 대해 #이 아니라면 접근이 가능하다. 코드 : #include int tp[10][10][10], p[1001], s[1001]; int find(int u) { if (u == p[u]) return u; return p[u] = find(p[u]); } void merge(int u, int v) { u = find(u), v = find(v); i..