글 읽기 - 반례를 알고 싶습니다!!!

success 1년 전 0

풀이를 보면 dfs나 bfs를 이용해서 풀던데 dfs,bfs를 이용하지 않고 풀면 안되나요? ㅠㅠ

반례를 찾고 싶습니다!

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int arr[20001];
vector<pair<int, int>> vec;
bool check(int x, int y)
{
    if (arr[x] == 0 && arr[y] == 0)
        arr[x] = 1, arr[y] = 2;
    else if (arr[x] == 0 && arr[y] != 0)
    {
        if (arr[y] == 1)
            arr[x] = 2;
        else
            arr[x] = 1;
    }
    else if (arr[y] == 0 && arr[x] != 0)
    {
        if (arr[x] == 1)
            arr[y] = 2;
        else
            arr[y] = 1;
    }
    else
    {
        if (arr[x] == arr[y])
            return false;
    }
    return true;
}
int main(void)
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        bool flag = true;
        int v, e;
        cin >> v >> e;
        for (int j = 0; j < e; j++)
        {
            int x, y;
            cin >> x >> y;
            if (x > y)
                vec.push_back({y, x});
            else
                vec.push_back({x, y});
        }
        sort(vec.begin(), vec.end());
        for (int k = 0; k < vec.size(); k++)
            flag = check(vec[k].first, vec[k].second);
        if (flag)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
        memset(arr, 0, (v + 1) * sizeof(int)); //
        vec.erase(vec.begin(), vec.end());     //
    }
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 알고 싶습니다!!!

success 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말