글 읽기 - 질문게시판에서 고수님들이 찾아주신 반례들 다통과했는데 계속안되네요 도와주세요 ㅠㅠ

kmslkh 4년 전 0

1707번 질문게시판에 있는 반레는 거의 다해봤습니다. 보면서 안되는곳 수정도하고 이제 게시판에 있는 반례도 다 통과했는데

문제통과는 안되네요 ㅠㅠ

답을 알려주시는게아니라 어디가 틀린건지 힌트라도 주실수 있을까요

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int v,e;
int visit[20001];
vector<int> g[20001];

void bfs(int z){
	int i;
	int tg=1;
	queue<int> q;
	q.push(z);
	visit[z]=tg;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(i=0;i<g[x].size();i++){
			if(visit[g[x][i]]==0){
				visit[g[x][i]]=visit[x]*(-1);
				q.push(g[x][i]);
			}			
		}		
	}
}

bool exist(int x,int y){          //x,y가 연결되어있는지 확인 되어있으면 true아니면 false 
	int i;
	for(i=0;i<g[x].size();i++){
		if(g[x][i]==y)
			return true;
	}
	return false;
}

bool findpath(int tg){     //같은 그룹으로 선택된 node에 대해서 연결이 있는지 확 인 
	int i,j;
	for(i=1;i<v;i++){
		if(visit[i]==tg){
			for(j=1;j<v;j++){
				if(visit[j]==tg&&exist(i,j))		
					return false;

		}
	}
}
return true;
}

int main(){
	int i;
	int T;
	cin>>T;
	
	while(T--){
		cin>>v>>e;
		v=v+1;
		for(i=0;i<=v;i++){
			g[i].clear();
			visit[i]=0;
		}
		for(i=0;i<e;i++){
			int x,y;
			cin>>x>>y;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		
		for(i=1;i<v;i++){
		if(visit[i]==0)
			bfs(i);
		}
		

		if(findpath(1)&&findpath(-1)){
			cout<<"YES"<<endl;
		}
		else
			cout<<"NO"<<endl;

	}
	
}

djm03178 4년 전 1

정점이 20000개면 59번째 줄에서 v가 20001이 되고, 60번째 줄에서 루프를 20001까지 돌면서 g[20001].clear()를 호출하게 되는데 g에는 20001번째 원소가 없으므로 무슨 일이 일어날지 모릅니다. visit[20001]=0 도 마찬가지입니다.

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

문제

문제

출처

ICPC

질문게시판에서 고수님들이 찾아주신 반례들 다통과했는데 계속안되네요 도와주세요 ㅠㅠ

kmslkh 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말