글 읽기 - 1707 25%에서 계속 실패한 이유

st0 1년 전 0

인접리스트가 없는 정점이 있는 경우 이분 그래프가 아니라고 생각했는데 이분 그래프 정의를 다시 보니

연결 안된 정점은 고려할 필요가 없었습니다.

소스코드 62 - 64번 라인에서 연결 안된 정점 발견 시 NO를 출력하도록 했는데 저 분기를 지우니 통과 됐습니다.

#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

int K;

class Graph{
public:
    int N;
    vector<int> visited;
    vector<vector<int>> adj;

    Graph(){}
    Graph(int n) : N(n){
        visited.resize(N);
        adj.resize(N);
    }

    void addEdge(int v, int u){
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    bool bfs(int start){
        queue<int> q;
        q.push(start);
        visited[start] = 1;
        while(!q.empty()){
            int curr = q.front(); q.pop();
            for(int next : adj[curr]){
                if(visited[next] == 0){
                    q.push(next);
                    visited[next] = visited[curr] == 1 ? 2 : 1;
                }
                else{
                    if(visited[next] == visited[curr]){
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

int main(){
    scanf("%d",&K);
    for(int i=0; i<K; i++){
        int V, E;
        scanf("%d %d",&V, &E);
        Graph G(V);
        int v,u;
        for(int j=0;j<E; j++){
            scanf("%d %d", &v, &u);
            v--; u--;
            G.addEdge(v,u);
        }
        int error = 0;
        for(int k=0;k<V;k++){
            if(!G.adj[k].size()){
                error = 1;
                break;
            }
            else {
                if(!G.visited[k]){
                    if(!G.bfs(k)){
                        error = 1;
                        break;
                    }
                }
            }
        }
        if(!error) printf("YES\n");
        else printf("NO\n");
    }
}

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

문제

문제

출처

ICPC

1707 25%에서 계속 실패한 이유

st0 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말