[Codeforces 1176E] Cover it!

[Codeforces 1176E] Cover it!

문제 설명 :

undirected edge로 이루어진 그래프가 주어진다. 이 그래프에서 최대 floor(n/2)개의 node들을 선택하여 '선택된 node들과, 선택되지 않은 node간의 거리가 1'이 되기 위해서 어떻게 node를 선택해야 하는지 묻는 문제이다.

풀이 : 

풀이는 매우 간단하다. 아무 노드에서부터 다른 노드들까지의 최단거리를 구한다(bfs나 dfs를 이용하면 된다). 그러면 그 거리가 짝수인 node들과 홀수인 node들로 그룹이 나눠질텐데 두 그룹 중에서 원소의 개수가 더 작은 그룹이 곧 정답이 되는 것이다.

이것이 가능한 이유는 짝수 -> 홀수 -> 짝수 -> 홀수 .... 형태가 반드시 반복된다는 확신이 있기 때문이다. 현재의 노드가 홀수라면 이 노드는는 당연히 짝수노드로부터 왔을 것이고, 다음 목적지도 무조건 짝수노드일 것이기 때문이다. 따라서 짝수그룹 or 홀수그룹을 선택하면 반드시 나머지 그룹과 거리 1만에 연결된다는 확신을 할 수가 있는 것이다.

주의할 점 : 

-

배운 점 : 

오래 고민했던 문제였는데 풀이는 생각보다 간단했다. 

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
/*********************Contest Template***********************/
const int SIZE= 200009;
vector<int> graph[SIZE];
int visited[SIZE]={0};
vector<int> ans;
int V,E;
void init(){
    for(int i=1 ; i<=V ; i++){
        visited[i]=0;
        graph[i].clear();
    }
    ans.clear();
}
int main(){
    int Q;  scanf("%d",&Q);
    while(Q--){
        scanf("%d %d",&V,&E);
        for(int i=0 ; i<E ; i++){
            int u,v;    scanf("%d %d",&u,&v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        queue<pii> q;
        q.push({1,0});
        int dist[SIZE];
        for(int i=1 ; i<=V ; i++)
            dist[i]=1<<30;
        dist[1]=0;
        vector<int> even,odd;
        while(!q.empty()){
            int cur=q.front().first,d=q.front().second; 
            q.pop();
            if(dist[cur]&1) odd.push_back(cur);
            else even.push_back(cur);
            for(int next:graph[cur]){
                if(dist[next]==1<<30){
                    q.push({next,d+1});
                    dist[next]=d+1;
                }
            }
        }
        if(even.size()<odd.size()){
            printf("%d\n",even.size());
            showAll(even,SPACE);
        }
        else{
            printf("%d\n",odd.size());
            showAll(odd,SPACE);
        }
        printf("\n");
        init();
        
    }
    return 0;
}