글 읽기 - (스포주의) 잘못 구현한 오일러 회로에서 구현이 잘못된 부분을 못찾겠습니다.

pichulia 3년 전 0

안녕하세요.
제가 이 문제를 오랜 시간동안 못풀고있어서 출제자분께 좀 징징거렸는데(...)
구데기컵 출제진중 한분이 도와주셔서
'잘못 구현한 오일러 회로의 구현이 잘못'되었다는 답변을 얻었습니다.

하지만 해당 알고리즘은 에디토리얼에 적혀있는 방법 그대로
"어떤 점 si가 포함되지 않는 간선들에 대해서 사이클이 있으면 나가리"
를 그대로 구현했다고 생각합니다...

(일단 '같은 정점 쌍을 연결하는 두 간선도 없다.'는 문제 조건에 의해
사이클이 있다면 그 길이는 3 이상일 것이고,
따라서 pi, 그러니까 직전 정점이 아닌 간선들을 따라 내려가다보면
사이클 판단이 될거라고 생각했습니다.)

우선 다른 문제의 코드들은 정답에 영향을 안주기 때문에 지웠습니다.

어느 부분이 잘못 구현됐는지 궁금합니다.ㅠㅠ

감사합니다.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<complex>
#include<assert.h>
#include<math.h>
#include<string>
#include<deque>
#include<queue>
#include<string.h>
#include<set>
#include<map>
#include<unordered_map>
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
using piii = pair<int, pii>;
using pll = pair<lld, lld>;

// SKIP OTHER PROBLEMS.

// solved by editorial.
namespace P5 {
	int n, m;
	vector<int> v[200009];
	vector<int> w[200009];
	int mask[200009];
	bool dfs(int si, int pi) {
		mask[si] = 1;
		int i, j;
        int ting = 0;
		for (i = 0; i < w[si].size(); i++) {
			j = w[si][i];
			if (j == pi){
                if(ting == 0){
                    ting = 1;
                    continue;
                }
                else{
                    assert(false);
                    return true;
                }
            }
			if (mask[j] == 0) {
				if (dfs(j, si)) return true;
			}
			else {
				return true;
			}
		}
		return false;
	}
	bool test(int si) {
		int i, j, k;
		//removed edge
		for (i = 0; i < n; i++) {
			w[i].clear();
			for (j = 0; j < v[i].size(); j++) {
				if (i == si || v[i][j] == si)continue;
				w[i].push_back(v[i][j]);
			}
		}
		for (i = 0; i < n; i++) {
			mask[i] = 0;
		}
		for (i = 0; i < n; i++) {
			if (mask[i] == 0) {
				if (dfs(i, -1)) {
					return true;
				}
			}
		}
		return false;
	}
	bool valid[200009];
	void solve_oiler() {
		int i, j, k;
		scanf("%d %d", &n, &m);
		if (n == m) {
			printf("0\n");
		}
		else {
			for (i = 0; i < n; i++) {
				valid[i] = false;
                v[i].clear();
			}
			for (i = 0; i < m; i++) {
				scanf("%d %d", &j, &k);
				j--; k--;
                assert(j>=0 && j<n);
                assert(k>=0 && k<n);
				v[j].push_back(k);
				v[k].push_back(j);
			}
			for (i = 0; i < n; i++) {
				if (!test(i)) {
					valid[i] = true;
				}
			}
			vector<int> res;
			for (i = 0; i < n; i++) {
				if (!valid[i]) {
					res.push_back(i);
				}
			}
			sort(res.begin(), res.end());
			res.erase(unique(res.begin(), res.end()), res.end());
			printf("%d\n", res.size());
			for (i = 0; i < res.size(); i++) {
				printf("%d ", res[i] + 1);
			}
			printf("\n");
		}
	}
}

int main() {
	//P1::solve_deque_cheat();
	//P2::solve_psw();
	//P3::solve_mini();
	//P4::solve_ju();
	P5::solve_oiler();
}

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

문제

문제

출처

ICPC

(스포주의) 잘못 구현한 오일러 회로에서 구현이 잘못된 부분을 못찾겠습니다.

pichulia 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말