ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 1707번 C++ 풀이
    백준 2018. 11. 25. 18:29
    #include <iostream>
    #include <queue>
    #include <vector>
    using namespace std;

    int isVisited[20001];
    vector<int> buffer[20001];
    int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    for (auto z=0; z<t; z++){
    int v, e;
    cin >> v >> e;

    for (auto i = 1; i<=v; i++){
    isVisited[i] = 0;
    buffer[i].clear();
    }
    for (auto i = 0; i<e; i++){
    int to, from;
    cin >> to >> from;
    buffer[to].push_back(from);
    buffer[from].push_back(to);
    }

    bool isBipartite = true;
    for (auto i=1; i<=v; i++){
    if (isVisited[i] == 0){
    isVisited[i] = 1;
    queue<pair<int, int>> q;
    q.push(make_pair(i, 1));
    while (!q.empty()){
    auto top = q.front();
    q.pop();
    for (auto edge : buffer[top.first]){
    if (isVisited[edge] == 0){
    isVisited[edge] = 3 - top.second;
    q.push(make_pair(edge, isVisited[edge]));
    }
    }
    }
    }
    }
    for (auto i = 1; i<=v; i++){
    int top = isVisited[i];
    for (auto edge : buffer[i]){
    if (isVisited[edge] == top){
    isBipartite = false;
    }
    }
    }
    if (isBipartite){
    cout << "YES";
    }else {
    cout << "NO";
    }
    cout << '\n';

    }
    return 0;

    }


    '백준' 카테고리의 다른 글

    백준 2799번 C++ 풀이  (0) 2019.01.04
    백준 2468번 C++ 풀이  (0) 2018.11.25
    백준 14502번 C++ 풀이  (0) 2018.11.20
    백준 c++ 11053번 풀이  (0) 2018.11.19
    백준 11057번 c++ 풀이  (0) 2018.11.18

    댓글 0

Designed by Tistory.