글 읽기 - 반례 부탁드립니다

dk10211 3년 전 0

원래 모든 섬은 연결되어 있었으므로 1과 연결되지 않는 부분만 찾아서 1과 연결하면 된다고 생각했는데 혹시 1과 연결하는 방식으로는 구하지 못하는 경우도 있나요?

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>v[300005];
vector<int>ans;
int main() {
	int n, a, b;
	vector<int>::iterator iter;
	scanf("%d", &n);
	ans.resize(n + 1);
	n -= 2;
	ans[1] = 1;
	while (n--) {
		scanf("%d %d", &a, &b);
		if (ans[a] == 1) {
			ans[b] = 1;
			iter = v[b].begin();
			while (iter != v[b].end()) {
				ans[*iter] = 1;
				iter++;
			}
		}
		else if (ans[b] == 1) {
			ans[a] = 1;
			iter = v[a].begin();
			while (iter != v[a].end()) {
				ans[*iter] = 1;
				iter++;
			}
		}
		else {
			v[a].push_back(b);
			v[b].push_back(a);
		}
	}
	int i = 2;
	while (1) {
		if (ans[i] != 1) {
			printf("1 %d", i);
			return 0;
		}
		i++;
	}
}

mickeyjung 3년 전 0

저도 이렇게 프로그램했는데 틀려서 같이 질문 올립니다.

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> parent;
int ans[2];

int Find(int x){
    if(parent[x]==x)return x;
    return Find(parent[x]);
}

int main() {
	cin>>n;
	parent.resize(n+1);
	for(int i=1;i<=n;i++)
        parent[i]=i;
    for(int i=0;i<n-2;i++){
        int u,v;
        cin>>u>>v;
        parent[v]=u;
    }
    ans[0]=Find(1);
    for(int i=2;i<=n;i++){
        if(ans[0]!=Find(i)){
            ans[1]=Find(i);
            break;
        }
    }
    cout<<ans[0]<<' '<<ans[1];
}

malratz 3년 전 6

반례입니다.

8
1 2
3 4
3 5
7 8
6 7
5 2

dk10211 3년 전 0

갱신 안되는 경우가 있었네요.

감사합니다

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

문제

문제

출처

ICPC

반례 부탁드립니다

dk10211 3년 전 0

mickeyjung 3년 전 0

malratz 3년 전 6

dk10211 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말