글 읽기 - 시간 초과 나는 이유가 뭘까요?

parkcs1220 1년 전 0

재귀함수가 아닌 스택으로 접근했습니다. 시간초과가 나오는 이유가 뭘까요?

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#define MAX_SIZE 100000 + 1

using namespace std;

vector<int> graph[MAX_SIZE];
int visited[MAX_SIZE] = { 0 };
int cnt = 1;

void dfs(int start)
{
	stack<int> s;
	s.push(start);

	while (!s.empty())
	{
		int current = s.top();
		s.pop();

		if (!visited[current])
		{
			visited[current] = cnt;
			cnt++;
		}

		for (auto neighbor : graph[current])
		{
			if (!visited[neighbor])
			{
				s.push(neighbor);
			}
		}
	}
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, r;

	cin >> n >> m >> r;

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	for (int i = 1; i <= n; i++)
	{
		sort(graph[i].begin(), graph[i].end(),greater<int>());
	}

	dfs(r);

	for (int i = 1; i <= n; i++)
	{
		cout << visited[i] << endl;
	}

	return 0;
}

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

문제

문제

출처

ICPC

시간 초과 나는 이유가 뭘까요?

parkcs1220 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말