글 읽기 - 고수님들 이거 왜 시간초과 나는지 알려주세요ㅜ

wiz9243 6년 전 0

다른 사람들 얘기 들어보면 단순 bfs, dfs만으로도 시간초과 안나게 할 수 있다는게 그 전제 하에서는 이 코드가 가장 적합하다고 생각하는데 왜 시간초과나는지 모르겠네요ㅜ 다른 알고리즘 구현안하고 단순 이 알고리즘 만으로요ㅜㅜ

#include<stdio.h>
#include<iostream>
#include<queue>

using namespace std;

struct information {
	int start, end;
};

queue<information>map;
queue<int>q;
int check[10005];
int v[10005];

int main() {
	int m, n, x, y,count=0;
	information temp;

	scanf("%d %d", &n, &m);
	for ( int i = 0; i < m; i++ ) {
		scanf("%d", &y);
		scanf("%d", &x);
		temp.start = x;
		temp.end = y;
		map.push(temp);
	}
	
	for ( int k = 1; k <= n; k++ ) {
		q.push(k);
		check[k] = 1;
		while ( !q.empty() ) {
			for ( int i = 0; i < m; i++ ) {
				x = q.front();
				temp = map.front();
				if ( x == temp.start&&check[temp.end] == 0 ) {
					count++;
					check[temp.end] = 1;
					q.push(temp.end);
				}
				map.push(map.front());
				map.pop();
			}


			q.pop();
		}
		v[k] = count;
		count = 0;
		for ( int i = 1; i <= n; i++ )check[i] = 0;
		while ( !q.empty() )q.pop();
	}

	int max = v[1];
	for ( int i = 2; i <= n; i++ )if ( max < v[i] )max = v[i];

	for ( int i = 1; i <= n; i++ )if ( v[i] == max )printf("%d ", i);

	
	return 0;
}

kdk8361 6년 전 1

10000 10000

1 2

2 3

3 4

.....

10000 1

이렇게 루프가 형성되어 있다면 n^2이 걸리겠네요

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

문제

문제

출처

ICPC

고수님들 이거 왜 시간초과 나는지 알려주세요ㅜ

wiz9243 6년 전 0

kdk8361 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말