백준 문제풀이
백준 19240 - 장난감 동맹군 [C++]
Vermeil
2021. 1. 20. 14:50
19240번: 장난감 동맹군
당신은 N개의 동물 장난감을 이용하여 모의 전쟁 놀이를 하려고 한다. 장난감은 편의상 1부터 N까지 번호가 붙어있고, 당신은 이를 두 개의 동맹군으로 나누고 싶다. 다만 특정 장난감끼리 사
www.acmicpc.net
[DFS를 이용한 내 풀이]
1번 정점부터 dfs를 돌며 방문하지 않은 정점에 대해 팀의 색을 돌아가면서 입혀주었다.
그 후, 모든 간선에 대해 두 정점의 색이 같은지 확인해주었다.
파이썬으로 하니까 터져서 c++로 풀었다.
[소스 코드]
|
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
|
#include <iostream>
#include <vector>
using namespace std;
#define endl '\n'
vector<int> arr[303030];
bool visited[303030];
bool team[303030];
void dfs(int x, bool t1){
t1 = !t1;
visited[x] = true;
team[x] = t1;
for (int k : arr[x]){
if (!visited[k]){
dfs(k, t1);
}
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int tc, n, m;
int a, b;
bool t;
cin >> tc;
while (tc--){
cin >> n >> m;
for (int i = 0; i < m; ++i){
cin >> a >> b;
arr[a].push_back(b);
arr[b].push_back(a);
}
fill(visited, visited+303030, false);
fill(team, team+303030, false);
t = false;
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i, t);
}
}
bool can = true;
for (int i = 1; i <= n; ++i){
for (int j : arr[i]){
if (team[i] == team[j]){
can = false;
}
}
}
if (can){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
for (int i = 1; i <= n; ++i){
arr[i].clear();
}
}
return 0;
}
|
cs |
아싸 1등이다
오타, 오류 지적 환영합니다.