글 읽기 - [c++] 19240번 백준 질문입니다.

gi5005 3년 전 0

임의의 노드를 하나 잡은 후, dfs로 탐색하면서 건너건너 갈때마다 팀을 표시해주고 , 만약에 인접 노드인데 같은 팀일 경우가 있을경우 false를 반환하도록 했는데 어디서 잘못된건지 모르겠습니다.

#include <bits/stdc++.h>
using namespace std;
#define INF (2 << 32) - 1
#define MAX 3000

bool dfs(int cur, int curT,vector<int> *E, vector<int> &team)
{
    bool ans = true;
    team[cur] = curT;
    for (int i = 0; i < E[cur].size(); i++)
    {
        int nx = E[cur][i];
        int nxT = (curT == 1) ? 2 : 1;
        if (team[nx] == curT)
        {
            return false;
        }
        if (team[nx] == 0)
        {
            ans &= dfs(nx,nxT,E,team);
        }
    }
    return ans;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        int N, M;
        cin >> N >> M;
        vector<int> team(300010,0);
        vector<int> E[MAX];
        for (int i = 0; i < M; i++)
        {
            int node1, node2;
            cin >> node1 >> node2;
            E[node1].push_back(node2);
            E[node2].push_back(node1);
        }
        string ans="NO\n";
        if(dfs(1,1,E,team)) ans ="YES\n";
        cout << ans;
    }
}

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

문제

문제

출처

ICPC

[c++] 19240번 백준 질문입니다.

gi5005 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말