https://www.acmicpc.net/problem/1707
가령 1--2--3--4
이러한 연결 관계를 가지는 그래프가 주어지면, 1을 빨간색, 2를 초록색으로 칠하고, 다시 3을 빨간색 4를 초록색
이렇게 두 가지의 색을 이용하여, 그래프의 모든 노드를 인접한 노드의 삭과 다른 색으로 색칠 할 수 있는지
검증하는 문제이다.
색깔의 구현은, 방문 처리 배열의 값을 1과 2사이에서 토글되게 하였다. 0이면 방문하지 않은것
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 | #pragma warning(disable :4996) #include<iostream> #include<vector> #include<queue> using namespace std; vector<int> grp[20001]; int vis[20001]; //초기 0, 두종류 1,2 -> 인접한 정점간에 다른 vis 값을 가지면 이분그래프 int vCnt, eCnt; bool isBigrp = true; queue<int> q; void bfs(int st) { q.push(st); vis[st] = 1; while (!q.empty()) { int cur = q.front(); q.pop(); for (int i = 0; i < grp[cur].size(); i++) { int next = grp[cur][i]; //확인할 지점 if (vis[next] != 0 && vis[cur] == vis[next]) { //인접한 정점과 같은 vis값을 가지는 경우 cout << "NO\n"; isBigrp = false; return; } if (vis[next] > 0) continue; //재방문 못하게 q.push(next); vis[next] = vis[cur] % 2 + 1; //cur이 1이면 next는 2가되고, vice versa } } } int main(void) { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { cin >> vCnt >> eCnt; for (int i = 0; i < eCnt; i++) { int src, dst; cin >> src >> dst; grp[src].push_back(dst); grp[dst].push_back(src); } for (int i = 1; i <= vCnt; i++) { if (vis[i] == 0) { bfs(i); if (!isBigrp) break; // 이분그래프가 아니라는 결론이 났으면 더 진행할 필요가 없다 } } if(isBigrp) cout << "YES\n"; //이 아래로는 초기화 부분 while (!q.empty()) q.pop(); for (int i = 1; i <= vCnt; i++) { vis[i] = 0; grp[i].clear(); } isBigrp = true; } return 0; } | cs |
'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글
백준 1157번: 단어 공부 (C++) (0) | 2019.09.25 |
---|---|
백준 10809번: 알파벳 찾기 (C++) (0) | 2019.09.25 |
백준 1389번: 케빈 베이컨의 6단계 법칙 (C++) (0) | 2019.09.25 |
백준 2644번: 촌수계산 (C++) (0) | 2019.09.25 |
백준 11724번: 연결 요소의 개수 (C++) (0) | 2019.09.25 |