Submission #1189068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189068		JungPS	Network (BOI15_net)	C++20	0 / 100	0 ms	324 KiB

net

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

vector<int> vec[2007];
vector<int> edge;
vector<int> cp;
bool visited[2007];
void dfs(int x,int p){
    if(visited[x]) return ;
    visited[x]=true;
    if(vec[x].size()==1 || p==-1) edge.push_back(x);
    for(auto i:vec[x]){
        if(i==p) continue;
        if(visited[i]) continue;
        dfs(i,x);
    }
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n; cin >> n;
    for(int i=0;i<n-1;++i){
        int a,b; cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    int mn=1e9;
    for(int i=1;i<=n;++i){
        memset(visited,0,sizeof(visited));
        edge.clear();
        dfs(i,-1);
        if(edge.size()<mn){
            mn=edge.size();
            cp=edge;
        }
    }
    cout << cp.size()-1 << '\n';
    for(int i=1;i<cp.size();++i){
        cout << cp[0] << " " << cp[i] << '\n';
    }
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37