글 읽기 - 시간 초과....멀 더 줄여야 할런지?

y3rr0r 6년 전 0

시간 단축을 위해

1. 탐색후 사이클과 연결은 됬으나 사이클은 아닌 노드는 아예 불가능한 노드로 식별자를 붙여서 다시 탐색하지 않도록 하고

2. 자식 노드쪽으로 입력되지 않은 숫자는 아예 탐색할 필요도 없는 것 같아서 탐색 대상에서도 제외 했습니다.

84%까지 진행하다가 시간 초과라네요...

뭘 더해야할지 힌트 부탁드려요

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int N,cycle,flag;
int Visit[100001];
int Result[100001];
vector<int> M;
vector<int> G[100001];
queue<int> Q;

void bfs(int r)
{
	int tmp;
	int cnt=1;
	if(Visit[r]!=0)
		return;
	Visit[r]=1;
	Q.push(r);
	M.push_back(r);

	while(!Q.empty())
	{
		tmp=Q.front();
		Q.pop();

		if(Visit[G[tmp][0]]==1)
		{			
			Visit[G[tmp][0]]=2;
			int c=1;	

			for(int i=0;i<M.size();i++)
			{
				if(M[i]==G[tmp][0])
				{
					c=M.size()-i;
					Visit[M[i]]=2; //사이클 형성 된 곳은 2로 표기
					flag=1;  //사이클 팀이란 표시
				}
				else if(flag==1)
				{
					Visit[M[i]]=2; //사이클 팀인 곳은 2로 표기
				}
				else
				{
					Visit[M[i]]=3; //비사이클로 확정된 곳은 3으로 표기
				}
			}

			for(int j=0;j<M.size()-c;j++)
				Visit[M[j]]=3; //비사이클로 확정 가능한 곳은 3으로 표기

			cycle-=c;
		}
		else if(Visit[G[tmp][0]]==0) //방문하지 않았던 곳 탐색
		{
			cnt++;
			Visit[G[tmp][0]]=1;
			Q.push(G[tmp][0]);
			M.push_back(G[tmp][0]);
		}
        else if(Visit[G[tmp][0]]==3) //다음 위치가 3이라면 지금 호출한 애는 사이클 형성이 불가능함. 
		{
			Visit[tmp]=3;
		}
	}
    if(flag==0) 
	{ //사이클 형성이 안됬으므로 들어갔던 위치는 모두 0으로 리셋...
		for(int i=0;i<M.size();i++)
		{
            if(i<M.size()-1)
				Visit[M[i]]=3;
			Visit[M[i]]=0;
		}
	}
		flag=0;
		M.clear();
}

 main()
{	
	int e=0,T=0;
	int temp[100001];	
	scanf("%d",&T);

	for(int i=0;i<T;i++)
	{
		scanf("%d",&N);
		cycle=N;
		for(int j=1;j<=N;j++)
		{
			scanf("%d",&e);
			G[j].push_back(e); //e로 들어오지 않는 값은 탐색 할 필요도 없음 
		    temp[e]=1;
		}

		for(int a=1;a<=N;a++)
		{
			if(temp[a]==1)
				bfs(a);		
		}

		Result[i]=cycle;
			
		for(int a=1;a<=N;a++)
		{			
            Visit[a]=0;
            temp[a]=0;
			G[a].clear();
		}		
	}
	
	for(int i=0;i<T;i++)
		printf("%d\n",Result[i]);
		
}

y3rr0r 6년 전 0

for(int i=0;i<M.size();i++)
  {
       //     if(i<M.size()-1)
    Visit[M[i]]=3;
   // Visit[M[i]]=0;
  }

위와같이 바꾸니 되네요

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

문제

문제

출처

ICPC

시간 초과....멀 더 줄여야 할런지?

y3rr0r 6년 전 0

y3rr0r 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말