글 읽기 - 4803 반례

rrsscc95 3년 전 0

4803번 반례가 궁금해서 질문 올려봅니다. 코드는 dfs를 통해 사이클을 파악하고, cycle을 제외한 tree 개수를 더해주는 코드입니다. 20퍼센트에서 틀렸다고 뜨는 상황인데 반례 알려주실 분 계신가요

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int n,m;
vector <int> node[501];
bool visited[501][2];//for cycle;
int numoftree=0;
int case_n=0;
int flag=0;//

void initialize(){
	numoftree=0;	
	case_n++;
	flag=0;
	memset(visited,false,sizeof(visited));
}

void dfs(int s,int up){
	visited[s][0]=true;
	visited[s][1]=true;
	for(int i=0;i<node[s].size();i++){
		int node_n = node[s][i];
		if(node_n==up)
			continue;
		else if(visited[node_n][0]==true)
			flag=1;
		else
			dfs(node_n,s);
	}	
}


void cal_tree(){
	for(int i=1;i<=n;i++){
		if(visited[i][1]==true)
			continue;
		dfs(i,-1);
		if(!flag)
			numoftree+=1;
		flag=0;
	}
			
	
	if(!numoftree)
		printf("Case %d: No trees\n",case_n);
	else if(numoftree==1)
		printf("Case %d: There is one tree\n",case_n);
	else
		printf("Case %d: A forest of %d trees.\n",case_n,numoftree);
	
}

int main(){
	int v1,v2;
	
	while(scanf("%d %d",&n,&m)&&n!=0){
		for(int i=0;i<m;i++){
			scanf("%d %d",&v1,&v2);
			node[v1].push_back(v2);
			node[v2].push_back(v1);
		}
		initialize();
		cal_tree();
		for(int i=0;i<n;i++)node[i].clear();
	}
	return 0;
}

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

문제

문제

출처

ICPC

4803 반례

rrsscc95 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말