글 읽기 - 왜 틀렸나요...?

lg970325 7년 전 0

인접행렬로 풀려고 했는데

틀렸다고 떠요...

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void)
{
    int a,b,i,j,x,y,count=0;
    scanf("%d",&a);
    scanf("%d",&b);
    
    int *visited=(int*)malloc(sizeof(int)*a);
    visited[0]=1;
    for(i=1;i<a;i++)
        visited[i]=0;
    
    int** G=(int**)malloc(sizeof(int*)*a);
    for(i=0;i<a;i++)
        G[i]=(int*)malloc(sizeof(int)*a);
    
    for(i=0;i<a;i++)
    {
        for(j=0;j<a;j++)
            G[i][j]=0;
    }
   
    for(i=0;i<b;i++)
    {
        scanf("%d %d",&x,&y);
        G[x-1][y-1]++;
        G[y-1][x-1]++;
    }
    
    for(i=0;i<a;i++)
    {
        if(G[0][i]!=0)
        {
            visited[i]++;
            for(j=0;j<a;j++)
            {
                if(G[i][j]!=0&&visited[j]==0)
                    visited[j]++;
            }
        }
    }
    
    
    
    for(i=0;i<a;i++)
        if(visited[i]!=0)
            count++;
    
    printf("%d",count-1);
    
    for(i=0;i<a;i++)
        free(G[i]);
    
    free(G);
    
    return 0;
}

zlzmsrhak 7년 전 0

먼저 반례입니다.

1 2

2 3

3 4

지금 코드의 33~44번째 줄을 보면 0과 연결된 것 i, i와 연결된 것 j를 찾아서 체크해 주는 방식인데,

이런 식으로 코드를 작성하면 예제처럼 3단계 이상 연결된 컴퓨터는 체크가 되지 않습니다.

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

문제

문제

출처

ICPC

왜 틀렸나요...?

lg970325 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말