글 읽기 - c++로 코드 작성했는데 도움부탁드립니다.

louisdebroglie 4년 전 0

bfs를 이용해서 각 노드에 색을 칠하고(status 0이면 아직 안 칠함, 칠하면 이웃 노드와 다르게 1,2로 채우기)

dfs를 이용해서 각 노드마다 이웃하는 노드에 같은 status가 있는지 확인하여, 같은 것이 있으면 NO 띄우기

이런식으로 짜보았는데, 질문계시판에 있는 테스트케이스들도 잘 돌아가는데 '틀렸습니다'가 떠가지고 질문을 올려봅니다..

혹시라도 제가 놓친부분이 있으면 좋은 답변 부탁드리겠습니다.

감사합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

vector<int> adjacencylist[20001];
vector<bool> checkdfs(20001);
vector<bool> checkbfs(20001);
vector<int> status(20001); // status is the flag_color which is consisted of 0,1
queue<int> q;

//Using dfs to fill out status
void dfs(int x, int before){
    //Arrived at a certain point
    
    //checkdfs fillout
    checkdfs[x] = true;
    
    //status fillout
    if(status[before] == 1)
        status[x] = 2;
    else if(status[before] == 2)
        status[x] = 1;
    
    //Going to the next point
    for(int i=0;i<adjacencylist[x].size();i++){
        int y= adjacencylist[x][i];
        if(checkdfs[y] == false){
            dfs(y,x);
        }
    }
}

//Using bfs to check status
bool bfs(int x){
    //Starting point
    checkbfs[x]=true; q.push(x);
    
    while(!q.empty()){
        //Arrived at a certain point
        int k= q.front(); q.pop();
        
        //Going to the next point
        for(int i=0;i<adjacencylist[k].size();i++){
            int y= adjacencylist[k][i];
            
            if(checkbfs[y] == true && status[y] == status[k])
                return false;
            
            if(checkbfs[y] == false){
                checkbfs[y] = true; q.push(y);
            }
        }
    }
    return true;
}

int main(){
    int testcase=0;
    cin >> testcase;
    for(int i=0;i<testcase;i++){
        int node, edge;
        cin >> node >> edge;
        
        for(int i=0; i<edge;i++){
            int u,v;
            cin >> u >> v;
            
            adjacencylist[u].push_back(v);
            adjacencylist[v].push_back(u);
        }
        
        //sorting
        for(int i=1;i<=node;i++){
            sort(adjacencylist[i].begin(),adjacencylist[i].end());
        }
        
        //finding if there is a cycle which the consisting number of components is a odd number.
        
        // using dfs, we first fill out the status vector of the components
        for(int k=1;k<=node;k++){
            if(checkdfs[k] == false){
                status[k] =1;
                dfs(k,k);
            }
        }
        // using bfs, we check
        bool answ = true;
        for(int k=1;k<=node;k++){
            if(checkbfs[k]==false){
                if(answ){answ=bfs(k);}
            }
        }
        if(answ == false)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
        //descending memory of global objects
        //vector<int> adjacencylist[1001];
        //vector<bool> checkdfs(1001);
        //vector<bool> checkbfs(1001);
        //vector<int> status(1001);
        for(int i=0;i<node;i++){
            adjacencylist[i].clear();
            checkdfs[i]=0;
            checkbfs[i]=0;
            status[i]=0;
        }
    }
    return 0;
}

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

문제

문제

출처

ICPC

c++로 코드 작성했는데 도움부탁드립니다.

louisdebroglie 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말