1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
|
using namespace std;
using pii = pair<int, int>; const int maxn = 1111; int n, m; int dep[maxn], vis[maxn], pre[maxn]; vector<int> G[maxn]; vector<pii> root; int tot = 0;
int (int u) { int L = u, R = u; int v, d, len = 0; queue<int> q; set<int> id;
vis[u] = 1; dep[u] = 0; id.emplace(u); q.emplace(u); while(!q.empty()) { u = q.front(); q.pop(); id.emplace(u); for(auto v : G[u]) { if(vis[v]) continue; vis[v] = 1; dep[v] = dep[u] + 1; q.emplace(v); } } for(auto x : id) if(dep[x] > dep[L]) L = x; for(auto x : id) { dep[x] = 0; vis[x] = 0; } while(!q.empty()) q.pop(); vis[L] = 1; q.emplace(L); while(!q.empty()) { u = q.front(); q.pop(); for(auto v : G[u]) { if(vis[v]) continue; vis[v] = 1; dep[v] = dep[u] + 1; pre[v] = u; q.emplace(v); } }
for(auto x : id) if(dep[x] > dep[R]) R = x; for(auto x : id) len = max(len, dep[x]); bool flag = 0; while(pre[R] != -1) { if(dep[R] == max(len/2, len-len/2)) { root.emplace_back(R, len); flag = 1; break; } R = pre[R]; } if(!flag) root.emplace_back(R, len); return len; }
signed main() { int u, v; while(~scanf("%d%d", &n,&m)) { tot = 0; for(int i = 1; i <= n; i++) G[i].clear(); root.clear(); memset(pre, -1, sizeof pre); memset(vis, 0, sizeof vis); memset(dep, 0, sizeof dep); for(int i = 0; i < m; i++) { scanf("%d%d",&u,&v); G[u].emplace_back(v); G[v].emplace_back(u); } for(int i = 1; i <= n; i++) { if(!vis[i]) gao(i); } int rt = 1, len = -1; sort(root.begin(), root.end(), [](pii a, pii b) { return a.second > b.second; }); rt = root[0].first, len = root[0].second; vector<pii> edge; for(auto p : root) { if(p.first == rt) continue; edge.emplace_back(rt, p.first); G[rt].emplace_back(p.first); G[p.first].emplace_back(rt); } memset(vis, 0, sizeof vis); memset(dep, 0, sizeof dep); printf("%dn", gao(rt)); for(auto x : edge) printf("%d %dn", x.first, x.second); } return 0; }
|
近期评论