글 읽기 - 반례 찾기가 무척 힘드네요.

uss425 3년 전 0

색칠하는 방법이 아닌, 정점의 개수가 홀수개인 사이클의 유무를 판단하는 코드를 짰습니다.

그런데,, 도저히 반례를 찾을수가 없네요.. 고수님들의 도움이 필요합니닷

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

class Graph
{
private : 
	bool flag;
	bool oddCycle;
	stack<int> stk;
	int v, e, head, before, ccnt; //cycle을 이루고 있는 정점의 개수 
	vector<vector<int> > adj;
	vector<bool> visited;
	
public:
	Graph(int _v, int _e) 
		: v(_v), e(_e), flag(true), oddCycle(false), before(-1)
	{
		adj.resize(0);
		visited.resize(0);
	}

	void SortList()
	{
		for(int i=1; i<=v; i++)
			sort(adj[i].begin(), adj[i].end());
	}
	
	void Init(int _v, int _e)
	{
		v=_v; e=_e;
		head = 0; ccnt=0;
		adj.resize(v+1);
		visited.resize(v+1, false);
	}
	
	void AddEdge(int u, int v)
	{
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	void FindCycle(stack<int> stk)
	{
		int head = stk.top();
		bool flag;
		ccnt=0;
		
		stk.pop();
		
		while(!stk.empty())
		{			
			ccnt++;
			
			if(stk.top()==head)
			{
				flag = true;
				break;
			}
			stk.pop();
		}
		
		if(!flag) ccnt=0;
	}
	
	void DFS(int curr, int before)
	{
		if(visited[curr]) return;
		
		visited[curr]=true;
		stk.push(curr);
		
		for(int i=0; i<adj[curr].size(); i++)
		{
			int next = adj[curr][i];
			
			if(next == before) continue;
			
			if(visited[next])
			{
				head = next;
				stk.push(next);
				FindCycle(stk);
				stk.pop();
				
				if(ccnt%2==1)
					oddCycle=true;
			}
			
			DFS(next, curr);
		}

		stk.pop();
		return;
	}
	
	void ResetStk()
	{
		while(!stk.empty())
			stk.pop();
	}	
	
	bool IsOddCycleExist()
	{
		return oddCycle;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int k, v, e;
	
	cin>>k;
	
	while(k--)
	{
		Graph g(0, 0);	
		bool ansFlag=false;
		
		cin>>v>>e;
		
		g.Init(v, e);
		
		for(int i=0; i<e; i++)
		{
			int a, b;
			cin>>a>>b;
			g.AddEdge(a, b);
		}
		
		g.SortList();
		
		for(int i=1; i<=v; i++)
		{
			g.DFS(i, -1);
			
			g.ResetStk();
			
			if(g.IsOddCycleExist())	
			{
				ansFlag=true;
				break;
			}
		}
		if(ansFlag)
			cout<<"NO\n";
		else
			cout<<"YES\n";
		
	}
		
	return 0;
}

uss425 3년 전 1

아래 반례들은 모두 통과를 합니다..

shg9411 3년 전 2

답이 올바르게 출력되는게 맞나요?

shg9411 3년 전 2

위부터 차례대로 정답은

'YES', 'YES', 'NO', 'YES', 'YES', 'YES', 'YES', 'YES', 'YES', 'NO', 'YES'

shg9411 3년 전 1

오답을 출력하는 케이스 중 하나인데

답은 yes 출력은 no입니다.

1,3 - 2,4 로 나눠질 수 있습니다.

uss425 3년 전 0

uss425 3년 전 0

PC의 차이가 있을리는 없는데..

shg9411 3년 전 1

https://ideone.com/kxBUJn

C++ 사용자가 아니라서 온라인에서 컴파일 한 결과로 확인하였습니다.

uss425 3년 전 0

환경별로 출력이 차이가 나는 경우도 있나요..?

uss425 3년 전 0

우선 색칠 방법으로 해결은 했습니다 (ㅜ_ㅜ);;

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

문제

문제

출처

ICPC

반례 찾기가 무척 힘드네요.

uss425 3년 전 0

uss425 3년 전 1

shg9411 3년 전 2

shg9411 3년 전 2

shg9411 3년 전 1

uss425 3년 전 0

uss425 3년 전 0

shg9411 3년 전 1

uss425 3년 전 0

uss425 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말