1. 首页
2. DFS
3. 本页

UVALive 5920 Kingdom Roadmap

题意：~

思路：给定一个n个点，n-1条边，问添加少的边使原图变成一个双连通图。因为给定的就是一棵树，所以问题简单了很多。

#include <bits/stdc++.h>

using namespace std;
const int N = 100050;
vector<int> g[N];
vector<int> ans;
bool flag[N];

void dfs(int u, int f)
{
    if((int)g[u].size() == 1) ans.push_back(u);
    for(auto &i : g[u]) if(i != f) dfs(i, u);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin >> n)
    {
        for (int i = 1; i <= n; i++) g[i].clear();
        int u, v;
        fill(flag, flag + N + 1, false);
        for(int i = 0; i < n - 1; i++)
        {
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
            flag[v] = 1;
        }
        int r = 0;
        for(int i = 1; i <= n; i++)
        {
            if(!flag[i])
            {
                r = i;
                break;
            }
        }
        ans.clear();
        dfs(r, 0);
        int sz = (int)ans.size();
        cout << (sz + 1) / 2 << endl;
        for(int i = 0; i * 2 < sz; ++i) cout << ans[i] << " " << ans[i + sz / 2] << endl;
    }
    return 0;
}