Hueestory

graph의 모든 node를 빨강과 파랑으로 색칠하되, 모든 edge가 빨강과 파랑 node를 포함해야 한다위 그림에서 각 edge는 빨강과 초록 node를 포함하고 있으며, 같은 색의 두 node를 포함하는 edge는 존재하지 않는다=> 같은 색의 두 node를 포함하는 edge가 존재할 경우 해당 그래프는 이분 그래프가 아니다 bool isBipartite() { for (int i = 1; i - graph를 인접 리스트로 표현한 2D vector A에 대해 이분 그래프의 여부를 판단하는 예시 코드

#include #include #include #include #define X 1#define Y 2using namespace std;int v, e;vector> A;vector visited;void DFS(int start, int color);bool isBipartite();int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int k; cin >> k; // k 만큼 반복 for (int i = 0; i > v >> e; A.resize(v + 1); visited.resize(v + 1, 0); // 에지의 개수 만큼 반복 fo..

#include #include #include #include using namespace std;vector> A;vector visited;vector cnt;int max_visited = 0;void BFS (int node);int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; A.resize(n + 1); visited.resize(n + 1); cnt.resize(n + 1); for (int i = 0; i > a >> b; A[a].push_back(b); } for (int i = 0; i ..

#include #include #include #include using namespace std;vector> A;vector cnt;vector visited;void BFS(int node);int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m, k, x; cin >> n >> m >> k >> x; A.resize(n + 1); for (int i = 0; i > a >> b; A[a].push_back(b); } visited.resize(n + 1); for (int i = 0; i Q; Q.push(node); while (!..

초기 작업 : 인접 리스트로 그래프 표현, 방문 배열 초기화, 시작 노드를 스택에 삽입pop을 수행하여 노드를 꺼냄 → 꺼낸 노드를 탐색 순서에 기입→ 인접 노드를 스택에 삽입, 방문 배열 체크→ 스택에 값이 없을 때까지 반복, 다녀간 노드는 재삽입하지 않음 초기 작업 : 인접 리스트로 그래프 표현, 방문 배열 초기화, 시작 노드를 큐에 삽입큐에서 노드를 꺼냄 →  꺼낸 노드를 탐색 순서에 기입→ 인접 노드를 큐에 삽입, 방문 배열 체크→ 큐에 값이 없을 때까지 반복, 다녀간 노드는 재삽입하지 않음 vector> Avector> list = {{2,3}, {4,5}, {4}, {5}, {}};  vector>> Avector>> list = {{{2,8}, {3,3}}, {{4,4}, {5,15}}, {..

#include #include #include using namespace std;typedef long long ll;vector> A[10];ll gcd(ll a, ll b);void DFS(int node);ll ratio[10];bool visited[10];ll lcm;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; lcm = 1; for (int i = 0; i > a >> b >> p >> q; A[a].push_back(make_tuple(b, p, q)); A[b].push_back(make_tuple(a, q, p))..

#include #include using namespace std;typedef long long ll;ll gcd(ll a, ll b) { if (a % b == 0) return b; else return gcd(b, a % b);}int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll a, b; cin >> a >> b; ll c; if (a >= b) c = gcd(a, b); else if (a  1. 1로 이루어진 수라고 해도, 결국 최대공약수를 구하는 문제이다ex) a = 6, b = 3인 경우6 % 3 == 0, GCD = 3111111 % 111 == 0, G..