글 읽기 - 시간초과 문제 해결해주세요..

alohajihwan 8년 전 0

dfs의 시간복잡도는 O(V+E) 인걸로 알고 있습니다. 지금 이 문제에서는 V = 100000 E = 100000개 이므로 시간복잡도는 V로 10만 인데 왜 시간초과 가 나오는지 모르겠습니다. 각 노드당 간선이 하나이므로 tree edge , back edge 를 제외한 간선이면 return 시켜줘서 최소한 덜 연산하도록 코드를 작성하였습니다.

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

using namespace std;

vector<vector<int> >adj;

vector<int> discovered,finished;

int counter;
int n;
int ans = 0;
void dfs(int here)
{
	if(discovered[here] != -1) return;

	discovered[here] = counter++;

	if(finished[here] == 1) return;

	for(int i=0;i<adj[here].size();i++)
	{
		int there = adj[here][i];

		if(finished[there] == 1) continue;

		if(discovered[there] == -1)
			dfs(there);
		
		else if(discovered[here] < discovered[there])
			return;

		//back edge가 나오면 cycle 이다.
		else if(finished[there] == 0)
		{
			ans+= -discovered[there] + discovered[here]+1;
			finished[there] = 1;
		}
		else return;
	}
	finished[here] = 1;
}
void dfsAll()
{
	for(int i=1;i<=n;i++)
	{
		if(discovered[i] == -1)
		{
			counter = 0;
			dfs(i);
		}
	}
}
int main()
{
	int test;
	scanf("%d",&test);

	for(int t=0;t<test;t++)
	{
		scanf("%d",&n);
		adj = vector<vector<int> >(n+1);
		discovered = vector<int>(n+1,-1);
		finished =vector<int>(n+1,0);


		for(int i=1;i<=n;i++)
		{
			int a;
			scanf("%d",&a);
			adj[i].push_back(a);
		}
		ans = 0;
		dfsAll();
		printf("%d\n",n-ans);
	}
}

koosaga 8년 전 1

test case가 좀 빡빡하게 들어와서 dfs로는 풀 수 없게 만들어진거 같습니다. (600ms가 빠른 편이니..)

alohajihwan 8년 전 0

답변 감사합니다.

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

문제

문제

출처

ICPC

시간초과 문제 해결해주세요..

alohajihwan 8년 전 0

koosaga 8년 전 1

alohajihwan 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말