광그로

문제 : https://www.acmicpc.net/problem/10451 #include #include #include #include #include #include using namespace std; vector graph[1001]; bool visited[1001] = { false }; int edge_num, vertex_index;//edge_num = vertex_num int cnt = 0; void DFS(int position, int start_pos) { visited[position] = true; for (int i = 0; i < graph[position].size(); i++) { int next_position = graph[position][i]; if (nex..

문제 : https://www.acmicpc.net/problem/1707 모든 edge의 양 끝에 vetex가 존재할 때, 각 vertex의 색깔이 다를 경우, 이분 그래프의 조건을 충족시킨다. #include #include #include #include #include #include //edge의 양 끝 vertex는 서로 다른 색깔을 가져야한다. using namespace std; int vertex_num, edge_num; vector graph[20001]; int colored[20001];//0:none 1:blue 2:red void DFS(int position, int color) { colored[position] = color; for (int i = 0; i < graph..

문제 : https://www.acmicpc.net/problem/11724 graph를 행렬화 시켜서 bfs를 돌려보았더니, 시간이 오래걸리는 것이 느껴졌다.이전, 1260 문제 풀이(http://rhkdrmfh.tistory.com/30) 중 두번째의 방법과 유사하게 풀이하였다. 연결 요소가 N개 존재할 때, BFS 혹은 DFS는 N번 시행되어야한다.for (int i = 1; i > vertex_num >> edge_num; for (int i = 0; i > vertex_left >> vertex_right; graph[vertex_left].push_back(vertex_right); graph[vertex_right].push_back(vertex_l..

문제 : https://www.acmicpc.net/problem/1260 DFS BFS 1. GRAPH를 행렬화#include #include #include #include #include #include using namespace std; int arr[1020][1020]; bool visited[1020]; int vertex_num, edge_num; stack DFS_NUM; queue BFS_NUM; void DFS(int start) { visited[start] = true; cout start_vertex; for(int i=0; i> vertex1 >> vertex2; arr[vertex1][vertex2] = arr[vertex2][vertex1] = 1; } DFS(start_..