글 읽기 - FAQ 다 보고 했는데도... 14%에서 시간초과로 계속 걸립니다...

rhdtka21 5년 전 0

새로운 케이스 할때마다 memset을 이용해서 check는 초기화 하고, 어떤 케이스가 끝나기 전에 clear로 vector도 초기화 시켜줍니다.

그리고 1부터 N번째 node 모두 BFS로 찾는데... 뭐가 문제일까요?

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
vector<int> edge[20001];
int check[20001];

bool BFS(int node){
	memset(check, 0, sizeof(check));
	queue<int> q;
	q.push(node);
	check[node]=1;
	while(!q.empty() ){
		node = q.back();
		q.pop();
		for(int i=0; i< edge[node].size() ; i++){
			int next = edge[node][i];
			if(check[next]==0){
				q.push(next);
				check[next]=3 - check[node];
			}
			else if(check[next] == check[node]){
				return false;
			}
		}
	}
	return true;
}

int main(void){
	int input;
	cin>>input;
	while(input--){
		//initialize
		memset(check, 0, sizeof(check));
		int N, M;
		cin >> N >> M;
		while(M--){
			int temp1, temp2;
			cin>>temp1>>temp2;
			edge[temp1].push_back(temp2); 
			edge[temp2].push_back(temp1); 
		}
		for(int i=1; i<=N; i++){
			sort(edge[i].begin(), edge[i].end());
		}
		bool err=false;
		for(int i=1; i<=N; i++){
			if(BFS(i)==false){
				cout<<"NO"<<'\n';
				err = true;
				break;
			}
		}
		if(!err)
			cout<<"YES"<<'\n';
		for(int i=0; i<=N; i++){
			edge[i].clear();
		}
	}
	
	return 0;
}

rhdtka21 5년 전 0

cin, cout을 scanf, printf로 바꿔도 여전히 똑같이 시간초과네요...

djm03178 5년 전 0

모든 정점에서 BFS를 해야 한다는 말이 매번 방문을 초기화해야 한다는 뜻이 아니고, 모든 정점이 방문될 때까지 미방문된 정점들에 대한 BFS를 마저 해줘야 된다는 뜻입니다.

rhdtka21 5년 전 0

이렇게 수정했더니 틀렸습니다가 되네요...

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
vector<int> edge[20001];
int check[20001];

bool BFS(int node){
	queue<int> q;
	q.push(node);
	check[node]=1;
	while(!q.empty() ){
		node = q.back();
		q.pop();
		for(int i=0; i< edge[node].size() ; i++){
			int next = edge[node][i];
			if(check[next]==0){
				q.push(next);
				check[next]=3 - check[node];
			}
			else if(check[next] == check[node]){
				return false;
			}
		}
	}
	return true;
}

int main(void){
	int input;
	cin>>input;
	while(input--){
		//initialize
		memset(check, 0, sizeof(check));
		int N, M;
		cin >> N >> M;
		while(M--){
			int temp1, temp2;
			cin>>temp1>>temp2;
			edge[temp1].push_back(temp2); 
			edge[temp2].push_back(temp1); 
		}
		for(int i=1; i<=N; i++){
			sort(edge[i].begin(), edge[i].end());
		}
		bool err=false;
		for(int i=1; i<=N; i++){
			if(check[i]==0){
				if(BFS(i)==false){
					cout<<"NO"<<'\n';
					err = true;
					break;
				}
			}
		}
		if(!err)
			cout<<"YES"<<'\n';
		for(int i=0; i<=N; i++){
			edge[i].clear();
		}
	}
	
	return 0;
}

djm03178 5년 전 1

15번째 줄의 back만 front로 고치면 됩니다.

rhdtka21 5년 전 0

아... 정말 감사합니다.

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

문제

문제

출처

ICPC

FAQ 다 보고 했는데도... 14%에서 시간초과로 계속 걸립니다...

rhdtka21 5년 전 0

rhdtka21 5년 전 0

djm03178 5년 전 0

rhdtka21 5년 전 0

djm03178 5년 전 1

rhdtka21 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말