티스토리 뷰
백준 사이트 URL : https://www.acmicpc.net/problem/1707
문제 분석
입력 : 테스트크기 T, 정점의 개수 V, 간선의 개수 E, E개의 연결정보
출력 : 그래프가 이분 그래프를 이루는지에 대한 여부
제한 : 시간제한 2초, 메모리제한 128MB
아이디어 : 이분그래프가 맞는지 확인해주면된다.
: http://sanghoon9939.tistory.com/33 에서 확인 가능하다.
: 간단하게 visit 처리를 색으로 해준후 이미 visit된 정점을 확인할때 자신과 같은 색이면, NO처리를 해준다.
소스코드
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 | #include<iostream> #include<string> #include<vector> using namespace std; enum color{RED, BLUE}; vector <int> map[20001]; int vertex[20001]; string res = "YES"; int v, e; int cnt = 0; void dfs(int v_, int color) { vertex[v_] = color; cnt++; if (cnt == v) return; for (int i = 0; i < map[v_].size(); i++) { if (vertex[map[v_][i]] == -1) dfs(map[v_][i], (color + 1) % 2); if (vertex[map[v_][i]] == color) { res = "NO"; return; } } return; } int main() { int t; cin >> t; for (int i = 0; i < t; i++) { res = "YES"; for (int j = 0; j < 20001; j++) { vertex[j] = -1; map[j].clear(); } cin >> v >> e; for (int j = 0; j < e; j++) { int v_1, v_2; cin >> v_1 >> v_2; map[v_1].push_back(v_2); map[v_2].push_back(v_1); } for (int j = 1; j <= v; j++) { if (vertex[j] == -1) dfs(j,RED); } cout << res << endl; } return 0; } | cs |
'Problem Solving > Baekjoon' 카테고리의 다른 글
Baekjoon-2696)중앙값 구하기 (0) | 2017.11.20 |
---|---|
Baekjoon-2491) 수열 (0) | 2017.10.19 |
댓글