글 읽기 - 와... 진짜 왜틀릴가요 반례즘 찾아주세요

minjoonist 4년 전 0

그냥 BFS로 각 컴폰뒤 플로이드 워샬 최단거리 돌려서 구했는데

정말 왜 틀린지 모르겠습니다. 6시간만에 예제 통과해서 제출했는데 무자비한 틀렸습니다가...

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
#define MAX 101
using namespace std;

vector<vector<int>> graph(MAX);
vector<bool> visited(MAX, false);

void bfs(int start){
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while(!q.empty()){
        int curr=q.front(); q.pop();

        for(auto &x: graph[curr]){
            if(!visited[x]){
                visited[x]=true;
                q.push(x);
            }
        }
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int vertex, edge, groupCnt=0;
    vector<int> group[MAX];
    int dist[MAX][MAX]={};

    cin>>vertex>>edge;

    for(int i=1; i<=vertex; i++)
        for(int j=1; j<=vertex; j++)
            if(i!=j) dist[i][j]=INF;

    while(edge--){
        int u, v;
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        dist[u][v]=dist[v][u]=1;
    }

    for(int i=1; i<=vertex; i++){
        if(!visited[i]){
            bfs(i);
            groupCnt++;
        }
        group[groupCnt].push_back(i);
    }

    for(int k=1; k<=vertex; k++)
        for(int i=1; i<=vertex; i++)
            for(int j=1; j<=vertex; j++)
                dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);

    cout<<groupCnt<<'\n';

    for(int i=1; i<=groupCnt; i++){
        int minValue=INF, minIndex;
        for(auto &x: group[i]){
            int mx=0;
            for(auto &y: group[i]){
                if(dist[x][y]==INF) continue;
                mx=max(mx, dist[x][y]);
            }
            if(mx<minValue){
                minValue=mx;
                minIndex=x;
            }
        }
        cout<<minIndex<<'\n';
    }
    return 0;
}

minjoonist 4년 전 3

3시간동안 코드만 쳐다봐서 해결했습니다. 결정적인 틀린 부분은 56줄인데요,

꼭 1, 2, 3이 한 컴포넌트로 다음 4, 5, 6, 7이 같은 컴포넌트라는 보장이 없기 때문에

BFS를 할때마다 group에 추가했어야 했습니다. 혹시 몰라 미래에 고생할 사람들을 위해 코드를 올림니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 200
#define MAX 101
using namespace std;

int groupCnt=0;
vector<int> graph[MAX], group[MAX];
vector<bool> visited(MAX, false);

void bfs(int start){
    queue<int> q;

    q.push(start);
    visited[start] = true;
    group[groupCnt].push_back(start);

    while(!q.empty()){
        int curr=q.front(); q.pop();

        for(auto &x: graph[curr]){
            if(!visited[x]){
                visited[x]=true;
                group[groupCnt].push_back(x);
                q.push(x);
            }
        }
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int vertex, edge;
    int dist[MAX][MAX];

    cin>>vertex>>edge;

    for(int i=1; i<=vertex; i++)
        for(int j=1; j<=vertex; j++)
            dist[i][j]=(i==j ? 0:INF);

    while(edge--){
        int u, v;
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        dist[u][v]=dist[v][u]=1;
    }

    for(int i=1; i<=vertex; i++){
        if(!visited[i]){
            groupCnt++;
            bfs(i);
        }
    }

    for(int k=1; k<=vertex; k++)
        for(int i=1; i<=vertex; i++)
            for(int j=1; j<=vertex; j++)
                dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);

    vector<int> res;

    for(int i=1; i<=groupCnt; i++){
        int minValue=INF, minIndex;
        for(auto &x: group[i]){
            int mx=0;
            for(auto &y: group[i]){
                if(dist[x][y]==INF) while(1);
                mx=max(mx, dist[x][y]);
            }
            if(mx<minValue){
                minValue=mx;
                minIndex=x;
            }
        }
        res.push_back(minIndex);
    }
    cout<<res.size()<<'\n';

    sort(res.begin(), res.end());
    for(auto &i: res)
        cout<<i<<'\n';
    return 0;
}

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

문제

문제

출처

ICPC

와... 진짜 왜틀릴가요 반례즘 찾아주세요

minjoonist 4년 전 0

minjoonist 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말