글 읽기 - 2617 구슬 찾기

exqt 8년 전 0

구슬쌍을 간선으로 보고 방향그래프를 만들어 탐색하여 갈 수 있는 점이 절반을 넘으면 카운트 해주는 식으로 풀었는데 방문한 지점을 다시 가는 경우가 있나요?

주어진 구글쌍에서 사이클이 생기면 말이 안되는 것 같은데..

올려둔 소스의 주석에서 // 만 지우면 AC 뜹니다. 그대로 제출하면 런타임에러 떠요.

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
 
#define in cin
#define out cout
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPE(i,s,e) for(int i=(s); i<=(e); i++)
 
int n,m;
int visit[111111];
vector< int > e0[111111];
vector< int > e1[111111];
 
int foo(int key, int dir)
{
    //if(visit[key]) return 0;
    //visit[key] = 1;
 
    int s = 0;
    if( dir == 0 )
    {
        REP(i, e0[key].size()) s += foo(e0[key][i], dir);
    }
    else
    {
        REP(i, e1[key].size()) s += foo(e1[key][i], dir);
    }
 
    return s + 1;
}
 
int main()
{
    in >> n >> m;
    REP(i,m)
    {
        int x, y; in >> x >> y;
        e0[x].push_back(y);
        e1[y].push_back(x);
    }
 
    int res = 0;
    int flag = 0;
    REPE(i,1,n)
    {
        flag = 0;
 
        //REPE(j,1,n) visit[j] = 0;
        if(foo(i,0)-1 > n/2) flag = 1;
 
        //REPE(j,1,n) visit[j] = 0;
        if(foo(i,1)-1 > n/2) flag = 1;
 
        if(flag) res++;
    }
 
    out << res << endl;
 
    return 0;
}

exqt 8년 전 0

고민 해 본 결과, 사이클이 없어도 시간초과 나거나 답이 틀린 경우가 있을 수 있네요. 그렇다고해서 런타임 에러가 나는 것은 아닌것 같은데 좀 더 생각해 보겠습니다.

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

문제

문제

출처

ICPC

2617 구슬 찾기

exqt 8년 전 0

exqt 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말