글 읽기 - bfs로 tree갯수 구하기

yoodori5 3년 전 0

bfs로 이미 방문한 노드에 부모노드가 아닌 다른 노드가 연결 되었을 경우 istree값을 false로 지정하고, 나중에 istree값이 변경되지 않았으면 tree의 갯수를 저장하는 total값을 증가시켜 출력했습니다.

어디가 문제인지 잘 모르겠습니다.

#include<stdio.h>
#include<queue>
#include<vector>

using namespace std;

vector<int> arr[501];
bool visit[501]={false,};
int parent[501]={0};
queue<int> pu;

int n,m,count;

int bfs(){
	//트리의 개수를 출력하는 함수
	int total=0;
	bool istree=true;
	for(int i=1;i<=n;i++){
		if(!visit[i]){
			istree=true;
			visit[i]=true;
			pu.push(i);
	
		while(!pu.empty()){
			int now=pu.front();
			pu.pop();
			for(int j=0;j<arr[now].size();j++){
					if(visit[arr[now][j]] && parent[now]!=arr[now][j]){
						istree=false;
					}
					else if(visit[arr[now][j]]){
						continue;
					}
					else{
						visit[arr[now][j]]=true;
						parent[arr[now][j]]=now;
						pu.push(arr[now][j]);
					}
				}
			}
			if(istree) total++;
		}
	}
	return total;
}

int main(){
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0 && m==0) break;
		for(int i=1;i<=n;i++){
			arr[i].clear();
			visit[i]=false;
			parent[i]=0;
		}
		for(int i=0;i<m;i++){
			int a,b;
			scanf("%d %d",&a,&b);
			arr[a].push_back(b);
			arr[b].push_back(a);
		}
		count = bfs();
		if(count==0) printf("Case 3: No trees.\n");
		else if(count==1) printf("Case 2: There is one tree.\n");
		else printf("Case 1: A forest of %d trees.\n",count);
	}
}

pepper_mis 3년 전 0

출력부분만 수정하면 될 것 같습니다.

몇번째 테스트케이스인지 카운트해서 "Case %d: ~ " 로 고쳐주세요:)

yoodori5 3년 전 0

아앗.....

아...

감사합니다ㅋㅋㅋㅋㅋ

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

문제

문제

출처

ICPC

bfs로 tree갯수 구하기 - (틀렸습니다)

yoodori5 3년 전 0

pepper_mis 3년 전 0

yoodori5 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말