PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
DFS
PROBLEM:
There is an empty graph on N vertices.
You can perform the following operation:
- Choose an array C of length N such that 1 \leq C_i \leq N.
- For each pair (i, j) such that C_i = C_j, add the edge (i, j) to G.
You’re given a tree on N vertices. Find any sequence of operations that constructs this tree.
EXPLANATION:
Let’s analyze the operation a bit first.
We’ll call C_i the color of vertex i, so an operation involves coloring every vertex, and then adding an edge between every pair of vertices with the same color.
Note that if we ever give three or more vertices the same color, they’ll all have edge between them, forming a cycle.
However, our final goal is a tree, which is acyclic - meaning we will never do this.
So, each color must appear at most two times.
If a color appears once (or zero times), it won’t contribute to any new edges; whereas if a color appears twice, it’ll form exactly one edge.
Further, if two different edges share an endpoint, it’s not possible to create them both in the same operation since we’d need to color three vertices to do this, which as noted earlier isn’t allowed.
Note that this already gives us a lower bound on the answer: if \text{deg}_i is the degree of vertex i, namely the number of edges incident to it, we surely need at least \text{deg}_i operations to create them all.
So, a lower bound on the number of operations is the maximum degree of any vertex, i.e,
D = \max(\text{deg}_i).
To use exactly D operations, we’ll need to be able to reduce D by 1 with every operation we make.
Since we’re dealing with a tree, that’s indeed doable.
Perform a DFS. When at vertex u, before processing any of its children,
- If \text{deg}_u \neq D, ignore u.
- If the edge between u and its parent has already been selected, again ignore u.
- Otherwise, choose an edge between u and any child of u.
Note that since \text{deg}_u = D, and D is the maximum degree, u won’t be a leaf, and hence will have at least one child.
The one exception to this is if D = 1, but that’s only possible when the tree has two vertices and a single edge; and the bottom vertex will be matched with the top one anyway so there’s no issue.
This way, every vertex with degree D will have at least one incident edge chosen.
For each chosen edge, give its endpoints the same color (different from any other color, of course).
For each vertex with no chosen edge, give it its own color, not shared with any other vertex.
This ensures that every degree-D vertex will have its degree reduced by 1, thus reducing the maximum degree by 1 as well.
Simply repeat this process over and over again till every edge has been created - it will take exactly D steps.
Note that previously chosen edges mustn’t be chosen again, so make sure to delete them.
This will turn the tree into a forest - but that’s fine, you can simply run the DFS separately for each tree within the forest, the algorithm doesn’t change.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
vector<pll> adj[N];
vector<ll> col(N);
void dfs1(ll u, ll p, ll pc){
ll c = 1;
for(auto [v,id] : adj[u]){
if(v == p) conts;
if(c == pc) c++;
col[id] = c;
dfs1(v,u,c++);
}
}
void solve(int test_case){
ll n; cin >> n;
rep1(i,n){
adj[i].clear();
}
vector<pll> edges(n);
rep1(i,n-1){
ll u,v; cin >> u >> v;
edges[i] = {u,v};
adj[u].pb({v,i}), adj[v].pb({u,i});
}
dfs1(1,-1,-1);
ll ans = *max_element(col.begin()+1,col.begin()+n);
cout << ans << endl;
rep1(i,ans){
vector<ll> c(n+5);
ll ptr = 1;
rep1(j,n-1){
if(col[j] == i){
auto [u,v] = edges[j];
c[u] = c[v] = ptr++;
}
}
rep1(j,n){
if(!c[j]){
c[j] = ptr++;
}
}
rep1(j,n) cout << c[j] << " ";
cout << endl;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
adj = [ [] for _ in range(n+1) ]
for i in range(n-1):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
D = max(len(adj[i]) for i in range(1, n+1))
order = []
def dfs(u, p):
order.append(u)
for v in adj[u]:
if v != p: dfs(v, u)
dfs(1, 0)
print(D)
while D > 0:
c = [0]*(n+1)
col = 1
for u in order:
if c[u] > 0: continue
if len(adj[u]) < D: continue
for v in adj[u]:
if c[v] > 0: continue
c[u] = c[v] = col
col += 1
adj[u].remove(v)
adj[v].remove(u)
break
D -= 1
for u in order:
if c[u] == 0:
c[u] = col
col += 1
print(*c[1:])