글 읽기 - c++ 틀렸습니다(1976 여행가자)

akrnote 3년 전 0

어디가 틀렸는지 잘 모르겠습니다...도움부탁드려요..

#include <bits/stdc++.h>
 
int N,M;
int pr[201];


int findf(int a){
	if(pr[a]==a) return a;
	pr[a] = findf(pr[a]);
	return pr[a];
}

void merge(int a, int b){
	findf(a);
	findf(b);
	pr[b]=a;
}

int main(){
	scanf("%d",&N);
	scanf("%d",&M);
	pr[0] = 0;
	for(int i=1; i<=N;i++){
		pr[i]=i;
	}
	for(int i =1; i<=N;i++){
		for(int j=1; j<=N; j++){
			int x;
			scanf("%d",&x);
			if(x==1){
				if(findf(i)!=findf(j)){
					merge(i,j);	
				}
			}	
		}
	}	
	int k;
	bool flag = true;
	scanf("%d",&k);
	k=findf(k);
	
	for(int i=1; i<M; i++){
		int x;
		scanf("%d",&x);
		if(k!=findf(x)){
			flag=false;
			break;
		}
	}
	if(flag==false){
		printf("NO");
	}else{
			printf("YES");
	}

	return 0;
}

fbfbf1 3년 전 0

merge 함수가 잘못 되었습니다.

merge 함수의 매개변수로 들어온 값들을 합치는게 아니라

매개변수로 들어온 값들의 가장 루트 노드를 보고 합쳐야 됩니다.

a = findf(a);

b = find(b);

if(a == b) return; 만 추가 해주면 AC 받습니다.

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

문제

문제

출처

ICPC

c++ 틀렸습니다(1976 여행가자)

akrnote 3년 전 0

fbfbf1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말