글 읽기 - 시간초과 질문입니다!!!! 꼭한번 봐주시면 감사합니다ㅠㅠ

wjdwldud4190 7년 전 0

시간초과가 나오는 이유를 잘 모르겠습니다.. for문 같은 것을 많이 줄이고 쓸데 없는 부분을 많이 줄였는데 그래도 시간초과가 나오네요ㅠㅠ

혹시 시간복잡도에 대해 잘 아시는 분이 계시다면 한번만 봐주시면 감사하겠습니다. 너무 풀어보고 싶은데 답답하네요 ㅠㅠ

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

vector <int>vec[100001];
vector <int>cvec;

int check[100001];
int ccheck[100001];

int cnt=0;
int startNum;
int lastNum;

void dfs(int x)//사이클일떄와 아닐때 무조건 이 함수가 끝나면 cnt++이 되버린다. 
{
	ccheck[x] = 1;

	int size; 
	size = vec[x].size();

	for(int i = 0;i<size;i++)
	{
		cvec.push_back(vec[x][i]); //사이클인 원소를 기억하기 위해

		if((ccheck[vec[x][i]] == 0) && check[vec[x][i]]==0)
		{
			dfs(vec[x][i]);
		}

		else 
			return;
	}
}

int main()
{
	cvec.reserve(100001);

	int input;
	scanf("%d",&input);

	while(input--)
	{
		int vertex;
		scanf("%d",&vertex);

		for(int i = 1; i<=vertex;i++)
		{
			vec[i].clear();
			check[i]=0;

			int n;

			scanf("%d",&n);

			vec[i].push_back(n);
		}

		cnt = 0;

		for(int i = 1; i<=vertex ; i++)
		{
			memset(ccheck,0,sizeof(ccheck));

			if(check[i]==0) //check가 0이라면 아직 방문하지 않은 곳이므로 
			{
				cvec.push_back(i); // 처음 시작 노드를 대입한다. 
				dfs(i); //

				startNum = cvec.front();//처음 시작 노드와
				lastNum = cvec.back();//마지막 노드가

				if(startNum == lastNum)// 같으면 사이클이므로
				{
					cnt++; //사이클 개수를 증가시켜주고

					while(!cvec.empty()) 
					{
						check[cvec.back()]=1;// 사이클 벡터를 다시 방문하지 않도록 check해준다.
						cvec.pop_back(); //벡터를 비워준다.
					}
				}

				else //사이클이 아니면 
				{
					check[startNum] = 2; //시작 노드를 다시 방문하지 않도록
				}

				if(!cvec.empty())//벡터를 비워준다.
					cvec.clear();
			}
		}

		int result = 0;

		for(int i = 1; i<=vertex;i++) //체크가 1이면 사이클이므로 
		{
			if(check[i] == 1)
			{
				result ++; //개수를 증가시켜준다.
			}
		}

		printf("%d\n",vertex - result); // 전체 개수 - 사이클 개수
	}

	return 0;
}

orange4glace 7년 전 1

dfs를 돌면서 이미 visit된 정점을 만났을 때 그 정점을 V라고 하면,

정점 V가 현재 실행된 dfs에 의해 방문된 노드인지(상황 1) 아니면 이전에 돌린 dfs에 의해 방문된 노드인지(상황 2) 판단할 수 있습니다.

(상황 1)이라면 사이클을 찾은것이고, (상황 2)라면 사이클을 찾지 못한 경우입니다.

(상황 2)가 사이클을 찾지 못한 경우가 되는 이유는 각 정점은 단 하나의 간선만을 가지기때문입니다.

현재 코드를 보면 check를 dfs가 끝난 후에 int 1 또는 2로 하고있는데,

dfs 안에서 check를 해나가면서, 동시에 check[v]에 들어가는 값을 잘 조정해주면, 앞서 말한 방법을 구현할 수 있습니다.

orange4glace 7년 전 1

추가적으로 int 배열을 하나 더 선언하면 사이클을 찾았을 때 그 사이클에 포함된 정점의 개수가 몇개인지 dfs가 종료되었을 때 O(1)만에 알 수 있습니다.

wjdwldud4190 7년 전 1

정말 친절하게 설명해주셔서 감사합니다. 한번 해보겠습니다ㅠㅠ 정말 감사합니다.

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

문제

문제

출처

ICPC

시간초과 질문입니다!!!! 꼭한번 봐주시면 감사합니다ㅠㅠ

wjdwldud4190 7년 전 0

orange4glace 7년 전 1

orange4glace 7년 전 1

wjdwldud4190 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말