글 읽기 - 반례를 못찾겠습니다...

qwe123rt45 5년 전 0

계속 틀려서 게시판에 반례 넣어봤는데 다 되고 정점과 간선이 아무것도 없는 경우도 처리해줬습니다.

몇퍼센트 올라가는 것도 없이 그냥 바로 틀렸습니다라고 뜹니다 반례나 어디가 틀렸는지 도움 얻을 수 있을까요?

#include <stdio.h>

int temp[20001],temp2[20001],x[20001],y[20001],jung[1001];
int chk[1001],ans[1001],q[1001];
int now=1;

void dfs(int n1)
{
    int i,j;
    
    for(i=jung[n1-1]+1;i<=jung[n1];i++)
        if(chk[y[i]]==0)
        {
            chk[y[i]]++;
            ans[++now]=y[i];
            dfs(y[i]);
        }
}
       
int main()   
{
	int n,v,m,i,cnt=0,st=0,ed=0;

	scanf("%d%d%d",&n,&m,&v);
	for(i=1;i<=m;i++)
	{
	    cnt++;
		scanf("%d %d",&x[cnt],&y[cnt]);
		cnt++;
		x[cnt]=y[cnt-1];
		y[cnt]=x[cnt-1];
	}//양방향이라서 넣어주는 작업입니다.

	ms(x,y,1,2*m);
	for(i=1;i<=2*m;i++)
	    jung[x[i]]++;
	for(i=2;i<=n;i++)
	    jung[i]+=jung[i-1];//앞번호 개수를 구하는 배열입니다.
	
	chk[v]=1;
	ans[1]=v;
	dfs(v);
	for(i=1;i<=now;i++)
	    printf("%d ",ans[i]);
	printf("\n");//dfs
	
	
	for(i=1;i<=n;i++)
	    chk[i]=0;
	
	q[++st]=v;//bfs
	chk[v]=1;
	while(st>ed)
	{
	    ed++;
	    printf("%d ",q[ed]);
	    for(i=jung[q[ed]-1]+1;i<=jung[q[ed]];i++)
	        if(chk[y[i]]==0)
	        {
	            q[++st]=y[i];
	            chk[y[i]]=1;
	        }
	}
	printf("\n");
	
	return 0;
}
//밑에는 병합정렬입니다.
void ms(int a[],int b[],int left,int right)
{
	int mid=(left+right)/2;

	if(left<right)
	{
		ms(a,b,left,mid);
		ms(a,b,mid+1,right);
		m(a,b,left,right);
	}
}

void m(int a[],int b[],int left,int right)
{
	int mid=(left+right)/2;
	int n1=left,n2=mid+1;
	int num=left,i;

	while(n1<=mid&&n2<=right)
	{
		if(a[n1]<a[n2]||(a[n1]==a[n2]&&b[n1]<b[n2]))
		{
			temp[num]=a[n1];
			temp2[num++]=b[n1++];
		}
		else if(a[n1]>a[n2]||(a[n1]==a[n2]&&b[n1]>b[n2]))
		{
			temp[num]=a[n2];
			temp2[num++]=b[n2++];
		}
		else
		{
			temp[num]=a[n1];
			temp2[num]=b[n1++];
			temp[num]=a[n2];
			temp2[num++]=a[n2++];
		}
	}
	if(n1>mid)
		for(i=n2;i<=right;i++)
		{
			temp[num]=a[i];
			temp2[num++]=b[i];
		}
	else
		for(i=n1;i<=mid;i++)
		{
			temp[num]=a[i];
			temp2[num++]=b[i];
		}
	for(i=left;i<=right;i++)
	{
		a[i]=temp[i];
		b[i]=temp2[i];
	}
}

qwe123rt45 5년 전 0

병합정렬을 잘못 구현했었습니다.

해결했습니다

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

문제

문제

출처

ICPC

반례를 못찾겠습니다...

qwe123rt45 5년 전 0

qwe123rt45 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말