-
[BOJ] 11745: King’s Inspection
11745: King’s Inspection 풀이 M <= N+20이므로, 주어지는 그래프는 최대 20개의 간선만 제거하면 트리가 된다. 즉, 트리와 아주 유사하게 생겼다는 뜻이고, 이는 대부분 노드의 in/out degree가 1이라는 뜻이다. indegree 또는 outdegree가 2 이상인 노드를 special node로 두자. special node에서 다른 speical node까지의 경로를 압축하자. in/out degree가 1인 노드들을 모두 압축해서 하나의 간선으로 치는 것이다. 그러면 노드가 많아야 40개인 그래프가 나온다. 이 그래프에서 TSP를 하면 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll;...
-
[BOJ] 16168 : 퍼레이드
16168 : 퍼레이드 풀이 degree 짝수가 어쩌구 저쩌구 해서 풀어도 되는데 그냥 제곱 돌려도 된다. 근데 degree 어쩌구 저쩌구 할 때 유의해야 할 점은 connected graph가 아닐 수도 있어서 유니온파인드 같은 걸 해줘야한다. 잘 짜주면 된다. 코드 #include <cstdio> #include <cstdlib> #include <vector> using namespace std; int n, m, chk[3003][3003]; vector<int> gph[3003]; void dfs(int now, int num, int cnt) { if (cnt == m) { puts("YES"); exit(0); } for (int nxt : gph[now]) { if...
-
[BOJ] 8088 : Airports
8088 : Airports 풀이 n개의 노드에 대해, 각 노드의 degree가 주어진다. 주어진 입력에 맞게 그래프를 구성해서 간선들을 출력하는 문제이다. (불가능한 경우는 주어지지 않는다) 남은 degree의 수가 가장 큰 노드를, 그 다음으로 작은 애들이랑 하나씩 이어주자. 이런 작업을 degree가 0이 될 때까지 반복하자. 다시 말해, degree가 큰 순서대로 먼저 간선을 이어주면 된다. 그럼 된다. 증명(?) 주어지는 그래프는 항상 valid한 그래프이다. 그럼, 완성된 그래프에서 노드를 하나씩 제거한다고 가정해보자. degree가 가장 큰 노드부터 제거해보자. 그래프 G에서 degree가 가장...
-
[BOJ] 10451 : 순열 사이클
10451 : 순열 사이클 풀이 . 코드 #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; int t, n; vector<int> a[1001]; int ans, chk[1001]; void dfs(int now) { chk[now] = 1; for (int i = 0; i < a[now].size(); i++) if (chk[a[now][i]] != 1) dfs(a[now][i]); } int main() { cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) { int v; cin >> v;...
-
[BOJ] 10265 : MT
10265 : MT 풀이 , 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; using vi = vector<int>; const int n_ = 1e3 + 1; int n, k; int a[n_], vst[n_], cyc[n_], scc[n_], dph[n_], dp[n_]; vector<int> b[n_]; int c_dfs(int now, int dep, int num) { vst[now] = num, dph[now] = dep; if (vst[a[now]] == num) return dph[now] - dph[a[now]] + 1; return c_dfs(a[now], dep + 1, num); } int s_dfs(int now, int num) {...
-
[BOJ] 1068 : 트리
1068 : 트리 풀이 잘 짜주자. 코드 #include <stdio.h> int n, i, now, del, cnt, gph[51], idg[51]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &gph[i]); if (~gph[i]) idg[gph[i]]++; } scanf("%d", &del); if (gph[del] == -1) return !printf("0"); idg[gph[del]]--; for (i = 0; i < n; i++) { if (idg[i]) continue; cnt++; for (now = i; ~now; now = gph[now]) if (now == del) { cnt--; break; }...
-
[BOJ] 15562 : 네트워크
15562 : 네트워크 풀이 모든 정점에 대한 sum(max(outdegree - indegree, 0))이 답이다. for (i = 1 ~ n) ans += max(out[i] - in[i], 0); for (i = 1 ~ n) ans += d[i]; ans /= 2; for (i = 1 ~ n) ans += max(d[i], 0); 등등 degree를 관리하는 방식에 따라 같은 식을 여러가지로 변형할 수 있겠다. 어떤 정점의 outdegree가 indegree보다 크다는 것은 해당 정점을 하나보다 많은 네트워크로 분리해서 나누어서 다음 노드로 나아가야 함을 의미한다....
-
[BOJ] 10252 : 그리드 그래프
10252 : 그리드 그래프 풀이 항상 사이클을 만들 수 있다. 첫 번째 행을 제외하고 ㄹ 모양으로 돌다가 마지막에 첫 번재 행으로 돌아와서 올라가주면 된다. 코드 #include <stdio.h> int main() { int tc; for (scanf("%d", &tc); tc; tc--) { int n, m, i, j; scanf("%d %d", &n, &m); puts("1"); for (i = 0; i < m; i++) printf("(%d,%d)\n", 0, i); for (i = 1; i < n; i++) { if (i % 2) for (j =...
-
[BOJ] 2668 : 숫자고르기
2668 : 숫자고르기 풀이 사이클을 찾아주면 된다! 우아하게 코드를 작성해보자. 코드 #include <stdio.h> int n, cnt, CNT[101], a[101]; int gogo(int now, int start) { for (int i = 1; i <= n; i++) { now = a[now]; if (now == start) return (cnt++, CNT[now]++); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int i = 1; i <= n; i++) gogo(i, i);...
-
[BOJ] 1068 : 트리
1068 : 트리 풀이 리프 노드라는 것은, 들어오는 간선이 없다는 것. 코드 #include <stdio.h> int n, i, now, del, cnt, gph[51], idg[51]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &gph[i]); if (~gph[i]) idg[gph[i]]++; } scanf("%d", &del); if (gph[del] == -1) return ~printf("0"); idg[gph[del]]--; for (i = 0; i < n; i++) { if (idg[i]) continue; cnt++; for (now = i; ~now; now = gph[now]) if (now ==...
-
[BOJ] 11724 : 연결 요소의 개수
11724 : 연결 요소의 개수 풀이 느낌있게 깊이우선탐색 코드 #include <iostream> #include <vector> using namespace std; int n, m, ans, vst[1001]; vector<int> gph[1001]; void dfs(int now) { vst[now] = 1; for (int nxt : gph[now]) if (!vst[nxt]) dfs(nxt); } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> m; for (int i = 0, u, v; i < m; i++) { cin >> u >> v; gph[u].push_back(v), gph[v].push_back(u); } for (int i = 1; i <=...
-
[BOJ] 13560 : 축구게임
13560 : 축구게임 풀이 랑주의 정리! S[i] = a[1~i]의 합, S[1~k] >= kC2 S[n] = nC2 증명 코드 #include <stdio.h> #include <algorithm> int main() { int n, i, s = 0, a[10000]; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); std::sort(a, a + n); for (i = 0; i < n; i++) { s += a[i]; if (s < (i+1)*i/2) return ~printf("-1"); } printf("%d", s == n*(n-1)/2 ? 1 : -1);...
-
[BOJ] 14571 : 모래시계
14571 : 모래시계 풀이 임의의 두 인접한 사이클은 하나 또는 두개의 노드를 공유할 수 있으므로 두 경우의 수를 모두 구해서 겹치는 경우를 제거하자 컴비네이션으로 구하면 쉽게 구할 수 있다. 코드 #include <stdio.h> #include <vector> using namespace std; typedef long long ll; const int n_ = 200; int n, m, one[n_], two[n_][n_]; bool gph[n_][n_]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d %d",...
-
[BOJ] 2150 : Strongly Connected Component
2150 : Strongly Connected Component 풀이 scc를 구현하자! 다른 블로그에 좋은 scc 설명이 많으니까 나는 구현만 해야겠다 원래 stl stack 써서 짰는데 메모리 많이 먹길래 기분 나빠서(?) 배열로 바꿨다. 처음 코드가 타잔, 다음 코드가 코사라주이다. 코드 타잔 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; typedef vector<int> vi; const int v_ = 1e4 + 1; int v, e, cnt, pos, scc[v_], chk[v_], stk[v_]; vi gph[v_]; vector<vi> res; int dfs(int now) { chk[now] = ++cnt;...
-
[BOJ] 1412 : 일방통행
1412 : 일방통행 풀이 단방향과 양방향 간선이 섞여있는 그래프가 주어진다. 양방향 간선들을 모두 단방향 간선으로 바꾸었을 때, 사이클이 있는지 찾는 문제이다. 일단 솔루션부터 이야기하면, 양방향 간선들은 제껴두고 단방향 간선들만으로 사이클을 이루는지 검사하면 된다. 증명은 음… 증명이라고 하긴 뭐하지만 1->2, 1->3, 2->4, 3->4, 1-4, 2-3의 그래프를 가정하자. 단방향 간선들로 위상정렬을 하면, 1 2 3 4가 나올 것이다. 그리고 1-4와 2-3은 위상정렬 순서에 따라 단방향 간선으로 바꾸어주면 된다. (1->4, 2->3) 코드 #include <stdio.h> int n, vst[101], flag;...