글 읽기 - 어디 부분이 틀렸는지 잘 모르겠습니다.

uss425 5년 전 0

테스트 케이스는 다 잘나옵니다만..

어제 저녁부터 잡고 있는데 넘어갈 생각을 안하네요...

반례나 코드 오류 좀 알려주세요 ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Tree
{
private :
	int N; //정점의 개수 
	vector<vector<int> > nodes;
	vector<bool> visited1;
	vector<bool> visited2;
	bool flag;
	int Vcnt, Ecnt;
public:
	Tree(int n):N(n)
	{
		flag=false; Vcnt=Ecnt=0;
		nodes.resize(N+1);
		visited1.resize(N+1);
		visited1.assign(N+1, false);
		visited2.resize(N+1);
		visited2.assign(N+1, false);
	}
	
	void addEdge(int a, int b)
	{
		nodes[a].push_back(b);
		nodes[b].push_back(a);
	}
	
	void sortList()
	{
		for(int i=0; i<N; i++)
			sort(nodes[i].begin(), nodes[i].end());
	}
	
	int resetVal()
	{
		Ecnt=Vcnt=0; flag=false;
	}
	
	int numOfVertex(int curr)
	{
		if(nodes[curr].size()==0||visited1[curr])
			return Vcnt;
		
		visited1[curr]=true;
		Vcnt++;
		
		for(int i=0; i<nodes[curr].size(); i++)
		{
			int next=nodes[curr][i];
			numOfVertex(next);
		}
		
		return Vcnt;
	}
	
	int numOfEdge(int curr)
	{
		if(nodes[curr].size()==0||visited2[curr])
			return 0;
		
		visited2[curr]=true;
		
		for(int i=0; i<nodes[curr].size(); i++)
		{
			int next=nodes[curr][i];
			numOfEdge(next);
			Ecnt++;
		}
		
		return Ecnt/2;
	}
	
	int rmrNodeCnt()
	{
		int cnt=0;
		for(int i=1; i<=N; i++)
		{
			if(visited2[i]==false)
				cnt++;
		}	
		return cnt;
	}
};

int main()
{
	int n, m, temp=0, cnt=0, vcnt=0, ecnt=0;
	
	while(1)
	{
		cin>>n>>m;
		if(n==0 && m==0) break;
		Tree t(n);
		
		for(int i=0; i<m; i++)
		{
			int a, b; cin>>a>>b;
			t.addEdge(a, b);
		}
		t.sortList();
		
		for(int i=1; i<=n; i++)
		{
			ecnt=t.numOfEdge(i);
			t.resetVal();
			vcnt=t.numOfVertex(i);
			t.resetVal();
			
			if(vcnt==ecnt+1) cnt++;
		}
		cnt+=t.rmrNodeCnt();
		
		cout<<"Case "<<temp<<": ";
		if(cnt>=2) cout<<"A forest of "<<cnt<<" Trees.\n";
		else if(cnt>=1) cout<<"There is one tree.\n";
		else if(cnt==0) cout<<"No trees.\n";
		else cout<<"Exception\n";
		
		cnt=0;
		temp++;
	} 
	 
	return 0;
}

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

문제

문제

출처

ICPC

어디 부분이 틀렸는지 잘 모르겠습니다.

uss425 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말