글 읽기 - 스페셜 저지를 추가해주세요!

tlwpdus 5년 전 1

14690번 문제는 여러 답 중 임의로 하나를 출력하는 되는 문제로 스페셜 저지가 필요한 문제입니다.

이에 아래 스페셜 저지 코드의 주석에 달아놓은 아이디어를 통해 스페셜 저지를 구현했습니다.

그 이후 DM::OJ라는 저지에 제 답안(tlwpdus)을 제출해 맞음을 확인한 후 제 코드로 스페셜 저지를 테스팅한 결과 잘 돌아감을 확인했습니다.

아직 깃헙에 익숙하지 않아서(ㅠㅠㅠ) 일단 여기에다가 스페셜 저지 코드를 업로드하니 확인해보시고 스페셜 저지 추가해주시면 감사하겠습니다~~

/*
문제 설명 :
주어진 자연수 K(1<=K<=1e7)에 대해서
정점의 개수 N(1<=N<=5000), 간선의 개수 M(1<=M<=5000)인 양방향 연결그래프를 구성해,
정점 a에서 정점 b까지 갔다가 다시 정점 a로 돌아오는 동안 같은 간선을 두 번 이상 방문하지 않는 경로가 존재하는
자연수의 순서쌍 (a, b) (1<=a<b<=N)의 개수를 정확히 K개로 맞추는 문제입니다.
이 때 그래프는 self-loop가 허용되지는 않지만 multi-edge는 허용됩니다.

스페셜 저지 아이디어 :
그래프를 절선 BCC로 분리했을 때에 같은 BCC 내에 존재하는 두 정점 a, b를 잡으면 항상 a->b->a 동안 같은 간선을
두 번 이상 방문하지 않는 경로가 있음을 알 수 있습니다. 반면 서로 다른 BCC에 존재하는 a, b를 잡게 되면 BCC 압축한 그래프가
트리 형태라는 점에서 착안하면 a->b->a 경로 동안 같은 간선을 무조건 방문해야 함을 알 수 있습니다.
따라서 주어진 그래프가 연결 그래프인지 확인한 뒤, 절선 BCC를 통해 BCC를 분리해 각 BCC의 사이즈 s에 대해 s*(s-1)/2를 더한 값이
K와 일치하는지 확인하면 됩니다.
*/

#include <bits/stdc++.h>
#include <assert.h>

using namespace std;

const int MAXN = 5003;
int n, m, k; // 각각 출력의 정점 개수, 간선 개수, 입력의 K값을 의미합니다.
vector<int> lis[MAXN]; // 그래프 연결 리스트
int tim[MAXN], lnk[MAXN]; // 각각 dfs-order와 low-link를 저장합니다.
int col[MAXN]; // 각 BCC-component에 속한 정점의 수를 저장합니다.

int tc; // time-count로 dfs-order와 low-link를 저장할 때에 사용합니다.
int cc; // color-count로 현재까지 나온 BCC component의 개수를 저장합니다.
stack<int> st;
void dfs(int here, int p) { // 현재 위치 here, 방금 온 정점 p
    int cnt = 0; // here->p 방문한 횟수 (multi-edge가 존재하기 때문에 필요함)
    tim[here] = lnk[here] = tc; tc++;
    st.push(here);
    for (int &there : lis[here]) {
        if (there==p) { // 방금 온 정점을 본 경우
            if (cnt) lnk[here] = min(lnk[here],tim[there]); // 역간선
            else cnt++; // 트리 간선
            continue;
        }
        if (~tim[there]) { // 역간선, 정간선
            lnk[here] = min(lnk[here],tim[there]);
            continue;
        }
        dfs(there,here); // 트리 간선
        lnk[here] = min(lnk[here],lnk[there]);
    }
    if (lnk[here]==tim[here]) { // here가 BCC의 root
        while(!st.empty()) { // here까지 한 BCC
            int v = st.top(); st.pop();
            col[cc]++;
            if (v==here) break;
        }
        cc++;
    }
}

int main(int agrc, char **agrv){
    /* argv[1] 에는 입력 데이터의 파일 이름이 주어집니다. */
    FILE *in = fopen(agrv[1],"r");

    /* argv[2] 에는 "모범 답안"의 파일 이름이 주어집니다. */
    // FILE *sol = fopen(agrv[2],"r");
    // 본 문제에서는 모범답안이 필요하지 않습니다.

    /* argv[3] 에는 제출한 프로그램의 출력 결과를 가지고 있는 파일 이름이 주어집니다. */
    FILE *out = fopen(agrv[3],"r");

    /* 입력 (자연수 K) */
    fscanf(in,"%d",&k);
    fclose(in);

    // n, m 입력
    assert(fscanf(out,"%d%d",&n,&m)==2);
    // 문제 조건에 의해 1 <= n, m <= 5,000
    assert(n>=1&&n<=5000&&m>=1&&m<=5000);

    int i;
    for (i=0;i<m;i++) {
        int a, b;
        // a, b 입력
        assert(fscanf(out,"%d%d",&a,&b)==2);
        // 범위 확인
        assert(a>=1&&a<=n&&b>=1&&b<=n);
        // two "distinct" integers a_i and b_i
        assert(a!=b);

        // 양방향 간선
        a--; b--; // 0-base로 바꿔 저장합니다.
        lis[a].push_back(b);
        lis[b].push_back(a);
    }
    /* 그 이후 쓰레기 출력이 존재하면 안 됩니다. (assert) */
    assert(fscanf(out,"%d",&i)==-1);

    // O(n+m) DFS로 절선 BCC를 구현합니다.
    memset(tim,-1,sizeof(tim));
    dfs(0,-1);
    int good = 1;
    for (i=0;i<n;i++) {
        if (tim[i]<0) { // 방문되지 않았다면 not-connected이다.
            good = 0;
        }
    }
    assert(good);

    int sum = 0;
    for (i=0;i<cc;i++) sum += col[i]*(col[i]-1)/2; // 각 컴포넌트의 순서쌍 개수를 누적한다.
    assert(sum==k);
    
    fclose(out);

    return 0;
}

startlink 5년 전 1

재채점했습니다.

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

문제

문제

출처

ICPC

스페셜 저지를 추가해주세요!

tlwpdus 5년 전 1

startlink 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말