글 읽기 - C++ 반례 부탁드리겠습니다.

akrnote 3년 전 0

어떤 상황에서 틀리는 지 감이 잘 잡히지 않습니다. 부탁드립니다.

#include<iostream>
#include<vector>
using namespace std;
int n,m,k;
int pr[51]={0,};
void init(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int findf(int a){
    if(pr[a]==a) return a;
    pr[a]=findf(pr[a]);
    return pr[a];
}

void unionf(int a, int b){
    a=findf(a);
    b=findf(b);
    if(a==b) return;
    if(a>b){
        pr[a]=b;
    }else{
        pr[b]=a;
    }
}



int main(){
    init();
    cin >> n >> m;
    cin >> k;
    bool truth[n+1];
    
    vector<int> v[m+1];
    vector<int> tp;
    int checkpoint=-1;
    int answer = m;
    for(int i=1; i<=n; i++){
        truth[i]=false;
    }
    for(int i=1; i<=n; i++){
        pr[i]=i;
    }
    
    for(int i=0; i<k;i++){
        int x;
        cin >> x;
        truth[x]=true;
        tp.push_back(x);
        checkpoint=x;
    }
    for(int i=0; i<tp.size()-1; i++){
        unionf(tp[i],tp[i+1]);
    }
    for(int i=1; i<=m; i++){
        int x;
        cin >> x;
        int tmp[x+1];
        for(int j=1; j<=x; j++){
            int y;
            cin >> y;
            tmp[j]=y;
            v[i].push_back(y);
        }
        for(int j=1; j<x; j++){
            unionf(tmp[j],tmp[j+1]);
        }
    }
    for(int i=1; i<=n; i++){
        if(pr[checkpoint]==pr[i]){
            truth[i]=true;
        }
    }
    for(int i=1; i<=m; i++){
        for(int j=0; j<v[i].size(); j++){
            if(truth[v[i][j]]){
                answer--;
                break;
            }
        }
    }
    cout << answer;
}

choko100 1년 전 0

안녕하세요, 반례가 나오는 케이스가 있어 공유드립니다.

https://www.acmicpc.net/board/...

입력)

정답)

위의 코드 출력)

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

문제

문제

출처

ICPC

C++ 반례 부탁드리겠습니다.

akrnote 3년 전 0

choko100 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말