글 읽기 - 바로 틀렸습니다 뜹니다 왜?? (C++)

ajrwk384 4년 전 0

크루스칼 알고리즘 적용했습니다. 우선순위 큐로 가중치 최소값인 경우를 우선으로 꺼내고, union-find로 사이클 판단했습니다.

제출하자마자 틀렸습니다 뜨는데 반례가 있나요?

이것저것 테스트케이스 넣어도 다 통과인데,, 무엇을 놓치고 있는지 모르겠습니다. 후

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int parent[10001];

struct Info {
	int node1, node2, cost;

	Info(int node1, int node2, int cost) {
		this->node1 = node1;
		this->node2 = node2;
		this->cost = cost;
	}
};

struct cmp {
	bool operator()(Info &a, Info &b) {
		return a.cost > b.cost;
	}
};

void initParent() {
	for (int i = 1; i <= N; i++) parent[i] = i;
}

int findParent(int node) {
	if (parent[node] == node) return node;
	return parent[node] = findParent(parent[node]);
}

void unionSet(int &n1, int &n2) {
	int p1 = findParent(n1);
	int p2 = findParent(n2);

	if (p1 > p2) parent[p1] = p2;
	else parent[p2] = p1;
}

priority_queue<Info, vector<Info>, cmp> q;

int findAns() {
	initParent();
	int ans = 0, edge = 0;

	while (!q.empty()) {
		Info cur = q.top(); q.pop();
		//cout << cur.node1 << ", " << cur.node2 << " : " << cur.cost << '\n';
		//부모가 다르면, 즉 연결 X면
		if (parent[cur.node1] != parent[cur.node2]) {
			unionSet(cur.node1, cur.node2);
			ans += cur.cost;
			edge++;
		}
		if (edge == N - 1) break;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;

	int n1, n2, cost;

	for (int i = 0; i < M; i++) {
		cin >> n1 >> n2 >> cost;
		q.push(Info(n1, n2, cost));
	}
	cout << findAns();
	return 0;
}

wjsqjawns 4년 전 1

올려주신 코드의 52번째 줄을, 바로 해당 노드의 부모를 비교하지 마시고,

findParent 함수의 반환값끼리 비교하게 하시면

정답 처리가 됩니다.

ajrwk384 4년 전 1

와 저걸 놓쳤네요 븅X같이.. 감사합ㄴ디ㅏ ㅠㅠ

dltpwns0 9달 전 0

븅X 한명 추가합니다 ㅜㅜ
감사해요!

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

문제

문제

출처

ICPC

바로 틀렸습니다 뜹니다 왜?? (C++)

ajrwk384 4년 전 0

wjsqjawns 4년 전 1

ajrwk384 4년 전 1

dltpwns0 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말