글 읽기 - 시간초과 날만한 부분 대충이라도 집어만 주세요...

lsy980124 7년 전 0

혹시 괜찮으시다면 시간복잡도 어떻게 계산되는지도 부탁드립니다아...ㅠ

#include<stdio.h>
int N, M;
int h;
int hac[100001][2];
int MAX[10001];
void BFS()
{
	int i, j; int n = 0;
	int queue[100001][2];
	int visit[10001];
	for (i = 0; i <= N; i++)
		visit[i] = 0;
	int rear = 1; int front = 1;
	for (i = 1; i <= M; i++)
	{
		if (hac[i][0] == h)
		{
			queue[front][0] = h;
			queue[front++][1] = hac[i][1];
			n = 1; visit[h] = 1;
		}
	}
	while (rear < front)
	{
		int gone = 0;
		for (i = 1; i <= M; i++)
		{
			if (hac[i][0] == queue[rear][1] && visit[queue[rear][1]] == 0)
			{
				queue[front][0] = queue[rear][1];
				queue[front++][1] = hac[i][1];
				gone = 1; 
			}
		}
		if (gone == 1)
		{
			n++;
			visit[queue[rear][1]] = 1;
		}
		rear++;
	}
	MAX[h] = n;
	return;
}
int main()
{
	int i, j;
	int c = 1;
	int Maximum = 1;
	scanf("%d %d", &N, &M);
	for (i = 0; i < M; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		hac[c][0] = b;
		hac[c++][1] = a;
	}
	for (h = 1; h <= N; h++)
		BFS();
	for (i = 1; i <= N; i++)
	{
		if (MAX[i] >= Maximum)
		{
			Maximum = MAX[i];
		}
	}
	for (i = 1; i <= N; i++)
	{
		if(MAX[i]==Maximum)
			printf("%d ",i);
	}
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 날만한 부분 대충이라도 집어만 주세요...

lsy980124 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말