글 읽기 - 어떤 케이스에서 나가는지 잘 모르겠습니다.

plzrun 6년 전 0

in: in-degree를 표현

o: order를 표현

위상정렬 풀듯이 해결하려 하였으나... 저 코드가 어떤 케이스를 만족하지 못하는지 잘 모르겠습니다. ㅠ 도와주세요 ㅠㅠ

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
vector<vector<int> > v;
int in[1001],o[1001];
int main() {
    int tc; scanf("%d", &tc);
    while(tc--) {
        queue<int> q;
        memset(in, 0, sizeof(in));
        memset(o,0,sizeof(o));
        int k,m,p;
        scanf("%d%d%d",&k,&m,&p);
        v.clear(); v.resize(m+1, vector<int>());
        for(int i=0; i<p; i++) {
            int a,b; scanf("%d%d",&a,&b);
            v[a].push_back(b);
            in[b]++;
        }
        for(int i=1; i<=m; i++) {
            if(!in[i]) {
                q.push(i);
                o[i]=1;
            }
        }
        while(!q.empty()) {
            int x=q.front(); q.pop();
            for(int y: v[x]) {
                if(o[y]<o[x]) o[y]=o[x];
                else if(o[y]==o[x]) o[y]++;
                if(--in[y]==0) q.push(y);
            }
        }
        printf("%d %d\n",k,o[m]);
    }
    return 0;
}

yukariko 6년 전 1

제 코드랑 다른점은

else if(o[y]==o[x]) o[y]++; 이 작업을 in이 0일때 한번만 증가시켜주는것이 다른것 같습니다.

plzrun 6년 전 0

doju님이 알려주신 케이스 덕에

이미 pair를 써서 구하긴했는데

in이 0일때 한번만 증가시켜주는거로 되는군요~!

처음엔 음.. 그런가? 하고 좀 생각해보니 크~

감사합니다 :D

djm03178 6년 전 1

음... 이 질문 보고 AC 받기는 했는데... 왜 그래야 하는지 잘 모르겠네요.

1
1 9 8
1 3
2 3
4 6
5 6
3 9
6 9
7 8

8 9

가령 이런 테스트 케이스가 있다면, 1, 2, 4, 5, 7, 8의 순서가 1이고, 3, 6의 순서가 2이고, 3, 6, 8이 9에 연결되어 있으니까 최댓값인 2의 순서를 가지는 게 2개 있어서 9는 3의 순서를 가져야 맞는 게 아닌가요? 제 AC 받은 코드나 plzrun님 AC 받은 코드로 돌리면 2가 나오고, 틀린 코드로 돌리면 3이 나오는데, 왜 2가 나오는 게 맞는건지 잘 이해가 안 되네요. 아니면 제가 문제를 잘못 이해한 건지...

startlink 5년 전 0

데이터를 추가하고 재채점했습니다.

https://www.acmicpc.net/rejudg...

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

문제

문제

출처

ICPC

어떤 케이스에서 나가는지 잘 모르겠습니다.

plzrun 6년 전 0

yukariko 6년 전 1

plzrun 6년 전 0

djm03178 6년 전 1

startlink 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말