글 읽기 - 시간초과가 나는이유를 못찾겠습니다ㅜㅜ

dudwls0113 5년 전 0

혹시몰라서

cin cout도

printf scnaf로 바꿔주고,..

질문게시판 뒤져보면서 이리저리봣는데

다른분들이랑 코드형식은 비슷한거같은데

왜시간초과가날까요..

이중포문이랑 재귀함수쓰신분들 많은거같던데ㅜㅜ

제가놓치고있는 무언갈 찾아주실수있으신지요..?!

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

class node {
public:
	int num;
	node* linked[1001];
	bool is_visited=true;
	bool is_linked[1001];

	void make( node* n) {
		if (linked[n->num] != n) {
			linked[n->num] = n;
			is_linked[n->num] = true;
			n->linked[this->num] = this;
			n->is_linked[this->num] = true;
		}
	}
	node(int a) {
		num = a;
		is_visited = false;
		fill_n(is_linked, 1000, false);
	}
	node() {}
};

void DFS_R(node &node, int n) {
	printf("%d ", node.num);
	node.is_visited = true;
	for (int i = 1; i <= n; i++) {
		if (node.is_linked[i]) {
			if (!node.linked[i]->is_visited) {
				DFS_R(*node.linked[i], n);
			}
		}
	}
}

node node_arr[1001];
int main() {
	queue<node> q;

	int n, m, v;
//	cin >> n >> m >> v;
	scanf("%d %d %d", &n, &m, &v);
	int tmp1, tmp2;
	for (int i = 1; i <= n; i++) {
		node_arr[i] = node(i);
	}
	for (int i = 0; i < m; i++) {
//		cin >> tmp1 >> tmp2;
		scanf("%d %d", &tmp1, &tmp2);

		if (node_arr[tmp1].is_linked[tmp2]) {
			i--;
			continue;
		}
		else
			node_arr[tmp1].make(&node_arr[tmp2]);	
	}

	DFS_R(node_arr[v], n);
	printf("\n");

	for (int i = 1; i <= n; i++) {
		node_arr[i].is_visited=false;
	}


/////////////////////////////////////////////////////////////////////////////////////
	q.push(node_arr[v]);
	node_arr[v].is_visited = true;
	node tmp = node();
	while (!q.empty()) {
		tmp = q.front();
		q.pop();
		for (int i = 1; i <= n; i++) {
			if (i == tmp.num) continue;
			if (tmp.is_linked[i]) {
				if (!(tmp.linked[i]->is_visited)) {
					q.push(*tmp.linked[i]);
					tmp.linked[i]->is_visited = true;
				}
			}
		}
//		cout << tmp.num << " ";// << endl;
		printf("%d ", tmp.num);

		
	}

}

doju 5년 전 0

간선 정보는 총 M줄이 주어지며, 그 중에 중복된 쌍이 있을 수 있습니다. 표현이 애매하다고 생각해 수정 요청을 올렸습니다.

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

문제

문제

출처

ICPC

시간초과가 나는이유를 못찾겠습니다ㅜㅜ

dudwls0113 5년 전 0

doju 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말