algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

problem.txt (2693B)


      1 D. Caveman
      2 time limit per test2 seconds
      3 memory limit per test512 megabytes
      4 Monocarp drew an undirected graph with n
      5  vertices and m
      6  edges. He wants to color each vertex red or blue so that every vertex has at least one neighbor of the opposite color. He needs to calculate the number of colorings that suit him.
      7 
      8 Monocarp is a caveman: he knows only the numbers 1
      9 , 2
     10 , and "many" (any number greater than 2
     11 ). He does not know about zero, so if there are no valid colorings, his brain melts.
     12 
     13 Help Monocarp count the valid colorings in his language. Two colorings are considered different if at least one vertex has a different color in them.
     14 
     15 Input
     16 The first line contains an integer t
     17  (1≤t≤104
     18 ) — the number of test cases.
     19 
     20 The first line of each test case contains two integers n
     21  and m
     22  (3≤n≤3⋅105
     23 ; 0≤m≤min(n(n−1)2,3⋅105)
     24 ) — the number of vertices and edges.
     25 
     26 Each of the next m
     27  lines contains two integers ui
     28  and vi
     29  (1≤ui,vi≤n
     30 ) — the numbers of the vertices connected by the i
     31 -th edge. The graph has no self-loops or multiple edges.
     32 
     33 Additional constraints on the input:
     34 
     35 the sum of n
     36  over all test cases does not exceed 3⋅105
     37 ; also the sum of m
     38  over all test cases does not exceed 3⋅105
     39 .
     40 Output
     41 For each test case, print on a separate line:
     42 
     43 1 or 2, if the number of valid colorings is equal to 1
     44  or 2
     45  respectively;
     46 Many, if the number of valid colorings is greater than two;
     47 Brain Melt, if there are no valid colorings.
     48 
     49 ---
     50 
     51 - n vertices, m edges, undirected graph
     52 - two-coloring s.t. every vertex of a given color has at least one neighbor of the other color
     53 - Two colorings are considered different if at least one vertex has a different color in them.
     54     - this implies there are at least two colorings if a coloring is possible bc just swap the colors, no statement about isomorphism or the like
     55 
     56 - cases:
     57     - 2
     58     - many (>2)
     59     - brain melt (0)
     60 
     61 ---
     62 
     63 3 1
     64 1 2
     65 
     66 
     67 v := {1,2,3}
     68 e := {{1,2}}
     69 
     70 1 := blue
     71 2 := red
     72 3 := blue
     73 
     74 no possible colorings like this because 3 is disconnected. generally, if there's a single disjoint vertex 0 is the answer
     75 
     76 
     77 ---
     78 
     79 3 2
     80 1 2
     81 1 3
     82 
     83 
     84 {1,2,3}
     85 {{1,2}, {2,3}}
     86 
     87 1 := blue 
     88 2 := red
     89 3 := blue
     90 
     91 // heuristic: set the first element to be blue, second to red, unless first is red then second is blue (bipartite)
     92 
     93 flip the colors is another option so return 2
     94 
     95 ---
     96 
     97 3 3
     98 1 2
     99 2 3
    100 1 3
    101 
    102 {1,2,3}
    103 
    104 1,2 - 2,3 - 1,3
    105 
    106 1 := blue
    107 2 := red
    108 3 := blue
    109 
    110 since there's a cycle it seems we can do more colorings?
    111 
    112 option 2: invert opt 1
    113 
    114 option 3:
    115 
    116 1 := blue
    117 2 := blue
    118 3 := red
    119 
    120 ---
    121 
    122 4 3
    123 1 2
    124 2 3
    125 3 4
    126 
    127 {1,2,3,4}
    128 
    129 1 -> 2
    130 2 -> 3
    131 3 -> 4
    132 
    133 1 := blue
    134 2 := red
    135 3 := blue
    136 4 := red
    137 
    138 invert
    139 
    140 1 := blue
    141 2 := red
    142 3 := red
    143 4 := blue
    144 
    145 ---