글 읽기 - 오일러회로 질문 부탁드립니다

benoker 9년 전 0

소스는 JM BOOK을 참고하였습니다.

여러 테스트 결과 오일러 서킷 존재조건 (모든정점이 outdegree==indegree이고 하나의 컴포넌트로 구성)을 통과했는데

답이 틀렸네요..

문제에서 "양방향 그래프"라는 포인트가 찔리긴 했는데

그래서 확실히 하려고 방향 그래프로 가정하고 코딩했습니다.

#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
vector<vector<int> > adj;
vector<int> in,out;
int n;
void getEuler(int here, vector<int>& circuit){
    for(int there=1; there<adj.size(); ++there)
        while(adj[here][there]>0){
            adj[here][there]--;
        	adj[there][here]--;
            getEuler(there,circuit);
        }
    circuit.push_back(here);
}
int main(){
    int input,edges=0;
    scanf("%d",&n);
    vector<int> circuit;
    adj = vector<vector<int> >(n+1,vector<int>(n+1,0));
    in = out = vector<int>(n+1,0);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++){
        scanf("%d",&input);
        if(input>=1){
            edges+=input;
        	adj[i][j]=input;
            out[i]+=input;
            in[j]+=input;
        }
    }
    for(int i=1; i<=n; i++){
    	if(in[i] != out[i]){ //  <--- 정점 검사
            printf("-1");
            return 0;
        }
    }
    for(int i=1; i<=n; i++)
        if(out[i]){             
    		getEuler(i,circuit);
        	break;
		}
    if(edges/2+1 != circuit.size()){   // <--- 모든 간선을 거쳤는지 확인
        printf("-1");
        return 0;
    }
    reverse(circuit.begin(),circuit.end());
    for(int i=0; i<circuit.size(); i++)
        printf("%d ",circuit[i]);
}

yukariko 9년 전 1

-1 의 출력조건이 잘못되었습니다.

입력부분을 아래 소스와 같이 고치니 AC를 받았습니다.

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++){
            scanf("%d",&input);
            if(input>=1){
                edges+=input;
                adj[i][j]=input;
                out[i]+=input;
                in[j]+=input;
            }
    	}
        if(out[i]%2)return puts("-1"),0;
    }

benoker 9년 전 1

아. 감사합니다! 명쾌합니다 ㅋㅋㅋ

outdegree 자체가 그냥 정점갯수로 보면 되군요 !

무향그래프로 보고 해야하는데 제가 잘못했네요 ㅠ (<- 사실 이부분 아직 잘 이해가 안되지만 조금 고민해보겠습니다!)

ㅋㅋ 알려주셔서 감사합니다!

benoker 9년 전 0

yukariko
와 근데 다른 애기지만 `return` `puts("-1"),0; <- 이거 오타인줄 알고 넘겼는데 ㄷㄷ 마저 몰랐네요 한 수 배웁니다 ㅋㅋㅋ대단하십니다 ㅋㅋㅋ`

yukariko 9년 전 1

ㅋㅋ 여기서 문제풀떄나 사용하는것이라 실제로 쓰기는 좀...

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

문제

문제

출처

ICPC

오일러회로 질문 부탁드립니다

benoker 9년 전 0

yukariko 9년 전 1

benoker 9년 전 1

benoker 9년 전 0

yukariko
와 근데 다른 애기지만 `return` `puts("-1"),0; <- 이거 오타인줄 알고 넘겼는데 ㄷㄷ 마저 몰랐네요 한 수 배웁니다 ㅋㅋㅋ대단하십니다 ㅋㅋㅋ`

yukariko 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

오일러회로 질문 부탁드립니다

benoker 9년 전 0

yukariko 9년 전 1

benoker 9년 전 1

benoker 9년 전 0

yukariko 와 근데 다른 애기지만 return puts("-1"),0; <- 이거 오타인줄 알고 넘겼는데 ㄷㄷ 마저 몰랐네요 한 수 배웁니다 ㅋㅋㅋ대단하십니다 ㅋㅋㅋ

yukariko 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

yukariko
와 근데 다른 애기지만 `return` `puts("-1"),0; <- 이거 오타인줄 알고 넘겼는데 ㄷㄷ 마저 몰랐네요 한 수 배웁니다 ㅋㅋㅋ대단하십니다 ㅋㅋㅋ`