Why this randomize solution is correct (1176E — Cover it!) ?

Правка en3, от PouyaNavid, 2020-03-16 14:09:49

Hi,

Can anyone tell me why this randomize solution is correct ?

Problem : 1176E - Покрывай!
Problem statement : You are given an undirected unweighted connected graph consisting of n vertices and m edges. It is guaranteed that there are no self-loops or multiple edges in the given graph. Your task is to choose at most n / 2 vertices in this graph so each unchosen vertex is adjacent (in other words, connected by an edge) to at least one of chosen vertices.
Solution : 62626593

Теги #randomisation, nondeterministic, #dfs and similar, tree, #graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский PouyaNavid 2020-03-18 08:34:25 2 Tiny change: 'i,\n\n\n\nCa' -> 'i,\n\n\n\n\nCa'
en6 Английский PouyaNavid 2020-03-17 16:27:21 2 Tiny change: '26593]\n\n' -> '26593]\n\n\n'
en5 Английский PouyaNavid 2020-03-16 18:40:55 2 Tiny change: 'Hi,\n\n\nCan ' -> 'Hi,\n\n\n\nCan ' (published)
en4 Английский PouyaNavid 2020-03-16 14:10:47 30 Tiny change: 'e at most **n / 2** vertices ' -> 'e at most \lfloor\frac{n}{2}\rfloor vertices ' (saved to drafts)
en3 Английский PouyaNavid 2020-03-16 14:09:49 2 Tiny change: 'Hi,\n\nCan an' -> 'Hi,\n\n\nCan an'
en2 Английский PouyaNavid 2020-03-15 12:07:37 0 (published)
en1 Английский PouyaNavid 2020-03-15 12:07:20 596 Initial revision (saved to drafts)