Algorithm/BOJ
-
학교 가지마! - 1420Algorithm/BOJ 2020. 2. 12. 18:32
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 12..
-
축사 배정 - 2188Algorithm/BOJ 2020. 2. 11. 14:15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 //2188 - 축사 배정 #include #include #include using namespace std; #define INF 2000000000 int N, M; vector capa, flow; void init() { cin >> N >> M; capa = flow = vector(N+M+2, vector(N+M..
-
효율적인 해킹 - 1325Algorithm/BOJ 2020. 2. 11. 12:47
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 //1325 - 효율적인 해킹 #include #include using namespace std; int N, M; vector adj; vector visited; vector hacked; void init() { cin >> N >> M; adj = vector(N+1); hacked = vector(N+1); int x, y; for(int i = 0; i> x >> y; adj[y].push_back(x); ..
-
최소 스패닝 트리 - 1197Algorithm/BOJ 2020. 1. 30. 19:37
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 //최소 스패닝 트리 - 1197 #include #include #include using namespace std; int V, E; vector edges; struct DisjointSet { vector parent, rank; DisjointSet(int n) : parent(n+1), rank(n+1, 1) { for(int i = 1; ..
-
최대공약수와 최소공배수 - 2609Algorithm/BOJ 2020. 1. 20. 05:49
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 //2609 #include using namespace std; int gcd(int x, int y) { while (true) { if (x == 0) return y; else if (y == 0) return x; else if (x > y) x = x % y; else y = y % x; } } int main() { int x, y; cin >> x >> y; int a = gcd(x, y); cout
-
Strongly Connected Component - 2150Algorithm/BOJ 2020. 1. 20. 05:36
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 //백준 SCC - 2150 #include #include #include #include #include using namespace std; int V, E; vector adj; vector discovered; vector sccId; priority_queue ..
-
단절선 - 11400Algorithm/BOJ 2020. 1. 10. 15:20
무향그래프에서 dfs 스패닝트리를 만들고 특정 정점을 루트 노드로 하는 subtree에서 선조 노드로 갈수 있는 역방향 간선이 있는지 확인하는 방법을 사용해 풀었습니다. https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다. 그래프의 정점은 1..