제출 #1136557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136557		byunjaewoo	Newspapers (CEOI21_newspapers)	C++20	8 / 100	92 ms	584 KiB

newspapers

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1010;
int n, m;
vector<int> adj[N];
vector<int> v, ans;

void dfs(int curr, int prev) {
    bool flag=true;
    for(int next:adj[curr]) if(next!=prev && adj[next].size()!=1)
        dfs(next, curr), v.push_back(curr), flag=false;
    if(flag && adj[curr].size()!=1) v.push_back(curr);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    if(m>=n) {
        cout<<"NO\n"; return 0;
    }
    for(int i=1; i<=m; i++) {
        int u, v; cin>>u>>v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    cout<<"YES\n";
    if(n==1) {
        cout<<"1\n1"; return 0;
    }
    if(n==2) {
        cout<<"2\n1 1"; return 0;
    }
    for(int i=1; i<=n; i++) {
        v.clear();
        dfs(i, 0);
        if(ans.empty() || v.size()<ans.size()) ans=v;
    }

    set<int> s, t;
    for(int i=1; i<=n; i++) s.insert(i);
    for(int i:ans) {
        s.erase(i), t.clear();
        for(int j:s) for(int k:adj[j]) t.insert(k);
        s=t;
    }
    reverse(ans.begin(), ans.end());
    for(int i:ans) {
        s.erase(i), t.clear();
        for(int j:s) for(int k:adj[j]) t.insert(k);
        s=t;
    }
    reverse(ans.begin(), ans.end());

    cout<<2*ans.size()<<"\n";
    for(int i:ans) cout<<i<<" ";
    reverse(ans.begin(), ans.end());
    for(int i:ans) cout<<i<<" ";

    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 8 / 8
• Subtask 3: 0 / 80