그냥 하는 노트와 메모장

분류 - [ 오일러 경로 ] 전형적인 문제다. N-M+1 개의 수열에 대해 앞 정점(M개에서 맨 뒤만 빠진 배열)과 뒷 정점(M개에서 맨 앞만 빠진 배열)을 이어주고, 이 그래프에서 오일러 회로 및 경로를 찾는다(입력에 따라 회로인지 경로인지 판단해야 한다).다만 좀 까다롭다는 점은 정점이 담아야하는 것이 배열이기 때문에 이를 유의하여 소스를 짜주시면 되겠다. 좀 더 쉬운 버전의 문제로는 Tanya and Password (http://codeforces.com/contest/508/problem/D)이 문제는 http://coloredrabbit.tistory.com/37?category=729843에 해설도 적어놓았으니, BOJ 1591 수열 복원 문제가 어렵다면 코드포스 문제를 먼저 풀어보는 것을 ..

* 오일러 회로 * 백준 온라인 저지 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. (양/무방향 그래..