Artifact 5fae6e092a92d7c8ea4556f16ecf0b6ab070b0d0:
0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0040: 2f 2f 20 43 68 65 63 6b 20 74 68 65 20 67 69 76 // Check the giv
0050: 65 6e 20 6c 69 73 74 20 63 61 6e 20 62 65 20 61 en list can be a
0060: 20 64 65 67 72 65 65 20 6c 69 73 74 20 6f 66 20 degree list of
0070: 73 6f 6d 65 20 67 72 61 70 68 0a 2f 2f 20 20 20 some graph.//
0080: 4f 28 6e 5e 32 29 20 20 28 49 20 73 75 73 70 65 O(n^2) (I suspe
0090: 63 74 20 69 74 20 63 61 6e 20 62 65 20 6d 61 64 ct it can be mad
00a0: 65 20 66 61 73 74 65 72 2c 20 74 68 6f 75 67 68 e faster, though
00b0: 2e 2e 2e 29 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 ...).//.// Verif
00c0: 69 65 64 20 62 79 0a 2f 2f 20 20 20 2d 20 53 52 ied by.// - SR
00d0: 4d 20 33 39 38 20 44 69 76 31 20 4c 56 33 0a 2f M 398 Div1 LV3./
00e0: 2f 0a 2f 2f 28 28 0a 2f 2f 20 48 61 76 65 6c 2d /.//((.// Havel-
00f0: 48 61 6b 69 6d 69 0a 2f 2f 20 20 20 49 66 20 47 Hakimi.// If G
0100: 5b 30 5d 2c 20 2e 2e 2e 2c 20 47 5b 6e 5d 20 28 [0], ..., G[n] (
0110: 64 65 63 72 65 61 73 69 6e 67 29 20 69 73 20 67 decreasing) is g
0120: 72 61 70 68 69 63 61 6c 2c 0a 2f 2f 20 20 20 74 raphical,.// t
0130: 68 65 6e 20 47 5b 31 5d 2d 31 2c 20 47 5b 32 5d hen G[1]-1, G[2]
0140: 2d 31 2c 20 2e 2e 2e 2c 20 47 5b 47 5b 30 5d 5d -1, ..., G[G[0]]
0150: 2d 31 2c 20 47 5b 47 5b 30 5d 2b 31 5d 2c 20 2e -1, G[G[0]+1], .
0160: 2e 2c 20 47 5b 6e 5d 0a 2f 2f 20 20 20 69 73 20 ., G[n].// is
0170: 61 6c 73 6f 20 67 72 61 70 68 69 63 61 6c 2e 0a also graphical..
0180: 2f 2f 29 29 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d //)).//---------
0190: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
01a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
01b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
01c0: 2d 2d 2d 2d 0a 0a 62 6f 6f 6c 20 69 73 47 72 61 ----..bool isGra
01d0: 70 68 69 63 61 6c 28 20 76 65 63 74 6f 72 3c 69 phical( vector<i
01e0: 6e 74 3e 20 47 20 29 0a 7b 0a 09 73 6f 72 74 28 nt> G ).{..sort(
01f0: 20 47 2e 62 65 67 69 6e 28 29 2c 20 47 2e 65 6e G.begin(), G.en
0200: 64 28 29 20 29 3b 0a 0a 09 76 65 63 74 6f 72 3c d() );...vector<
0210: 69 6e 74 3e 3a 3a 69 74 65 72 61 74 6f 72 20 62 int>::iterator b
0220: 20 3d 20 6c 6f 77 65 72 5f 62 6f 75 6e 64 28 20 = lower_bound(
0230: 47 2e 62 65 67 69 6e 28 29 2c 20 47 2e 65 6e 64 G.begin(), G.end
0240: 28 29 2c 20 31 20 29 3b 0a 09 76 65 63 74 6f 72 (), 1 );..vector
0250: 3c 69 6e 74 3e 3a 3a 69 74 65 72 61 74 6f 72 20 <int>::iterator
0260: 65 20 3d 20 47 2e 65 6e 64 28 29 3b 0a 0a 09 77 e = G.end();...w
0270: 68 69 6c 65 28 20 62 20 3c 20 65 20 29 0a 09 7b hile( b < e )..{
0280: 0a 09 09 69 6e 74 20 6e 20 3d 20 2a 28 2d 2d 65 ...int n = *(--e
0290: 29 3b 0a 09 09 69 66 28 20 65 2d 62 20 3c 20 6e );...if( e-b < n
02a0: 20 29 0a 09 09 09 72 65 74 75 72 6e 20 66 61 6c )....return fal
02b0: 73 65 3b 0a 09 09 66 6f 72 28 76 65 63 74 6f 72 se;...for(vector
02c0: 3c 69 6e 74 3e 3a 3a 69 74 65 72 61 74 6f 72 20 <int>::iterator
02d0: 69 3d 65 2d 6e 3b 20 69 21 3d 65 3b 20 2b 2b 69 i=e-n; i!=e; ++i
02e0: 29 0a 09 09 09 2d 2d 2a 69 3b 0a 09 09 69 6e 70 )....--*i;...inp
02f0: 6c 61 63 65 5f 6d 65 72 67 65 28 20 62 2c 20 65 lace_merge( b, e
0300: 2d 6e 2c 20 65 20 29 3b 0a 09 09 62 20 3d 20 6c -n, e );...b = l
0310: 6f 77 65 72 5f 62 6f 75 6e 64 28 20 47 2e 62 65 ower_bound( G.be
0320: 67 69 6e 28 29 2c 20 47 2e 65 6e 64 28 29 2c 20 gin(), G.end(),
0330: 31 20 29 3b 0a 09 7d 0a 09 72 65 74 75 72 6e 20 1 );..}..return
0340: 74 72 75 65 3b 0a 7d 0a true;.}.