글 읽기 - 생각이 틀린거같은데, 반례도 궁금합니다 ㅠㅠ

gktgnjftm 5년 전 0

전형적인 유니온 파인드 문제라고 생각을했습니다

입력받은 순서의 반대로 친구가 아닐때 친구를 맺어서

만약에 알고보니 루트가 같다면(친구를 이미 맺어져있었다면) 말에 모순이 생겼다고 생각하여

아니라고 출력을 했습니다

생각이 딱히 증명되지는 않아서, 좋은 해법이 있다면 알려주시면 감사하겠습니당 ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
using namespace std;
typedef long long ll;
#define INF 1000000000
#define mod 1000000000
typedef pair<int, int> P;
typedef pair<pair<int, int>, int> PP;
typedef pair<int, pair<int, int>> PPP;
int gox[4] = { 0,1,-1,0};
int goy[4] = { 1,0,0,-1};
int parent[2005];
int n, m;
int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}
void uni(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	parent[u] = v;
}
int main() {
	scanf("%d%d", &n, &m);
	vector<P> v;
	for (int i = 1; i <= n; i++) parent[i] = i;
	for (int i = 0; i < m; i++) {
		int first, second;
		scanf("%d%d", &first, &second);
		v.push_back({ first,second });
	}
	int no = 0;
	for (int i = v.size() - 1; i >= 0; i--) {
		int ftop = find(v[i].first);
		int stop = find(v[i].second);
		if (ftop == stop) {
			no = 1;
			break;
		}
		uni(v[i].first,v[i].second);
	}
	if (no) printf("0\n");
	else printf("1\n");
	return 0;
}

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

문제

문제

출처

ICPC

생각이 틀린거같은데, 반례도 궁금합니다 ㅠㅠ

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말