백준 19240 - 장난감 동맹군 [C++]

www.acmicpc.net/problem/19240

19240번: 장난감 동맹군

 

 

[DFS를 이용한 내 풀이]

1번 정점부터 dfs를 돌며 방문하지 않은 정점에 대해 팀의 색을 돌아가면서 입혀주었다.

그 후, 모든 간선에 대해 두 정점의 색이 같은지 확인해주었다.

 

안 되는 예 (1, 3번 정점의 색이 같다)

 

 

 

파이썬으로 하니까 터져서 c++로 풀었다.

 

[소스 코드]

#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;
}
 

아싸 1등이다

 

오타, 오류 지적 환영합니다.