Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4220acb

Browse files
authored
Improved task 2508
1 parent777eb7b commit4220acb

File tree

2 files changed

+107
-60
lines changed
  • src
    • main/java/g2501_2600/s2508_add_edges_to_make_degrees_of_all_nodes_even
    • test/java/g2501_2600/s2508_add_edges_to_make_degrees_of_all_nodes_even

2 files changed

+107
-60
lines changed
Lines changed: 38 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -1,85 +1,63 @@
11
packageg2501_2600.s2508_add_edges_to_make_degrees_of_all_nodes_even;
22

3-
// #Hard #Hash_Table #Graph #2023_03_20_Time_33_ms_(100.00%)_Space_109.7_MB_(42.70%)
3+
// #Hard #Hash_Table #Graph #2023_04_18_Time_36_ms_(95.00%)_Space_86.3_MB_(93.33%)
44

55
importjava.util.ArrayList;
6-
importjava.util.HashSet;
76
importjava.util.List;
8-
importjava.util.Set;
97

108
@SuppressWarnings("unchecked")
119
publicclassSolution {
1210
publicbooleanisPossible(intn,List<List<Integer>>edges) {
13-
// first find odd edge nodes
14-
int[]degree =newint[n +1];
11+
ArrayList<Integer>[]g =newArrayList[n +1];
12+
ArrayList<Integer>oddList =newArrayList<>();
13+
for (inti =1;i <=n;i++) {
14+
g[i] =newArrayList<>();
15+
}
1516
for (List<Integer>edge :edges) {
16-
degree[edge.get(0)]++;
17-
degree[edge.get(1)]++;
17+
intx =edge.get(0);
18+
inty =edge.get(1);
19+
g[x].add(y);
20+
g[y].add(x);
1821
}
19-
List<Integer>oddNodes =newArrayList<>();
2022
for (inti =1;i <=n;i++) {
21-
if ((degree[i] &1) ==1) {
22-
oddNodes.add(i);
23-
}
24-
if (oddNodes.size() >4) {
25-
// cannot be larger than four
26-
returnfalse;
23+
if (g[i].size() %2 ==1) {
24+
oddList.add(i);
2725
}
2826
}
29-
if ((oddNodes.size() &1) ==1) {
30-
// can only have even numbers of odd nodes
31-
returnfalse;
32-
}elseif (oddNodes.isEmpty()) {
33-
// zero situation
27+
intsize =oddList.size();
28+
if (size ==0) {
3429
returntrue;
3530
}
36-
// find all edges of oddListNode
37-
Set[]adjList =newHashSet[oddNodes.size()];
38-
for (inti =0;i <oddNodes.size();i++) {
39-
adjList[i] =newHashSet<>();
31+
if (size ==1 ||size ==3 ||size >4) {
32+
returnfalse;
4033
}
41-
for (List<Integer>edge :edges) {
42-
for (inti =0;i <oddNodes.size();i++) {
43-
if ((int)edge.get(0) ==oddNodes.get(i)) {
44-
adjList[i].add(edge.get(1));
45-
}
46-
if ((int)edge.get(1) ==oddNodes.get(i)) {
47-
adjList[i].add(edge.get(0));
48-
}
34+
if (size ==2) {
35+
intx =oddList.get(0);
36+
inty =oddList.get(1);
37+
if (isNotConnected(x,y,g)) {
38+
returntrue;
4939
}
50-
}
51-
// to see if it is two or four
52-
if (oddNodes.size() ==4) {
53-
// can only connect each other
54-
// have to detect if they have an edge or not
55-
returnadjList[0].size() < (n -1)
56-
&&adjList[1].size() < (n -1)
57-
&&adjList[2].size() < (n -1)
58-
&&adjList[3].size() < (n -1)
59-
&& ((!adjList[0].contains(oddNodes.get(1))
60-
&& !adjList[1].contains(oddNodes.get(0))
61-
&& !adjList[2].contains(oddNodes.get(3))
62-
&& !adjList[3].contains(oddNodes.get(2)))
63-
|| (!adjList[0].contains(oddNodes.get(2))
64-
&& !adjList[2].contains(oddNodes.get(0))
65-
&& !adjList[1].contains(oddNodes.get(3))
66-
&& !adjList[3].contains(oddNodes.get(1)))
67-
|| (!adjList[0].contains(oddNodes.get(3))
68-
&& !adjList[1].contains(oddNodes.get(2))
69-
&& !adjList[2].contains(oddNodes.get(1))));
70-
}else {
71-
// if two dont have an edge, could use it
72-
if (adjList[0].contains(oddNodes.get(1))) {
73-
// need to find a spare node
74-
for (inti =1;i <=n;i++) {
75-
if (adjList[0].contains(i) ||adjList[1].contains(i)) {
76-
continue;
77-
}
40+
for (inti =1;i <=n;i++) {
41+
if (isNotConnected(i,x,g) &&isNotConnected(i,y,g)) {
7842
returntrue;
7943
}
80-
returnfalse;
8144
}
45+
returnfalse;
46+
}
47+
inta =oddList.get(0);
48+
intb =oddList.get(1);
49+
intc =oddList.get(2);
50+
intd =oddList.get(3);
51+
if (isNotConnected(a,b,g) &&isNotConnected(c,d,g)) {
8252
returntrue;
8353
}
54+
if (isNotConnected(a,c,g) &&isNotConnected(b,d,g)) {
55+
returntrue;
56+
}
57+
returnisNotConnected(a,d,g) &&isNotConnected(b,c,g);
58+
}
59+
60+
privatebooleanisNotConnected(intx,inty,ArrayList<Integer>[]g) {
61+
return !g[x].contains(y);
8462
}
8563
}

‎src/test/java/g2501_2600/s2508_add_edges_to_make_degrees_of_all_nodes_even/SolutionTest.java

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,4 +34,73 @@ void isPossible3() {
3434
.isPossible(4,ArrayUtils.getLists(newint[][] {{1,2}, {1,3}, {1,4}})),
3535
equalTo(false));
3636
}
37+
38+
@Test
39+
voidisPossible4() {
40+
assertThat(
41+
newSolution()
42+
.isPossible(
43+
21,
44+
ArrayUtils.getLists(
45+
newint[][] {
46+
{2,19}, {16,17}, {8,14}, {2,16}, {12,20}, {12,14},
47+
{16,18}, {15,16}, {10,21}, {3,5}, {13,18},
48+
{17,20}, {14,17}, {9,12}, {5,15}, {5,6}, {3,7},
49+
{2,21}, {10,13}, {8,16}, {7,18}, {4,6}, {9,1},
50+
{13,21}, {18,20}, {7,14}, {4,19}, {5,8}, {3,11},
51+
{11,1}, {7,12}, {4,7}, {3,16}, {13,17}, {17,19},
52+
{9,13}, {7,19}, {10,16}, {4,13}, {4,5}, {2,15},
53+
{12,19}, {11,16}, {2,9}, {11,17}, {17,1}, {16,21},
54+
{4,10}, {10,14}, {14,16}, {4,1}, {13,20}, {5,20},
55+
{4,14}, {4,21}, {10,20}, {2,14}, {8,15}, {4,8},
56+
{6,19}, {15,1}, {19,1}, {8,19}, {15,21}, {3,12},
57+
{11,18}, {9,17}, {18,19}, {7,21}, {3,21}, {16,19},
58+
{11,15}, {5,1}, {8,17}, {3,15}, {8,1}, {10,19},
59+
{3,8}, {6,16}, {2,8}, {5,18}, {11,13}, {11,20},
60+
{14,21}, {6,20}, {4,20}, {12,13}, {5,12}, {10,11},
61+
{9,15}, {3,19}, {9,20}, {14,18}, {21,1}, {13,19},
62+
{8,21}, {2,13}, {3,10}, {9,18}, {19,21}, {6,7},
63+
{3,18}, {2,18}, {6,14}, {3,17}, {5,21}, {14,20},
64+
{8,9}, {16,1}, {3,4}, {13,1}, {5,9}, {4,15},
65+
{17,21}, {20,21}, {2,17}, {13,14}, {11,14},
66+
{9,16}, {10,18}, {6,15}, {6,12}, {3,13}, {5,11},
67+
{6,1}, {12,17}, {8,10}, {5,10}, {8,18}, {4,12},
68+
{10,1}, {6,13}, {4,18}, {7,20}, {7,16}, {2,6},
69+
{12,21}, {4,17}, {15,18}, {13,16}, {15,20},
70+
{7,10}, {6,10}, {2,20}, {7,15}, {18,1}, {12,1},
71+
{3,20}, {7,1}, {14,15}, {4,9}, {11,19}, {7,9},
72+
{5,17}, {18,21}, {6,21}, {8,11}, {6,17}, {3,14},
73+
{7,11}, {5,7}, {7,13}, {6,8}, {6,9}, {10,12},
74+
{5,16}, {2,4}, {17,18}, {9,11}, {12,16}, {3,6},
75+
{12,18}, {3,9}, {11,12}, {14,19}, {10,15}, {5,13},
76+
{8,13}, {15,17}, {2,10}, {11,21}, {20,1}, {6,18},
77+
{2,12}, {19,20}, {6,11}, {8,12}, {2,3}, {12,15},
78+
{2,11}, {9,10}, {7,17}, {9,19}, {13,15}, {7,8},
79+
{4,11}, {2,5}, {5,19}, {16,20}, {15,19}, {9,14},
80+
{14,1}, {10,17}, {9,21}, {2,7}, {8,20}, {5,14},
81+
{4,16}
82+
})),
83+
equalTo(true));
84+
}
85+
86+
@Test
87+
voidisPossible5() {
88+
assertThat(
89+
newSolution()
90+
.isPossible(
91+
6,
92+
ArrayUtils.getLists(
93+
newint[][] {{1,6}, {1,3}, {1,4}, {4,5}, {5,2}})),
94+
equalTo(true));
95+
}
96+
97+
@Test
98+
voidisPossible6() {
99+
assertThat(
100+
newSolution()
101+
.isPossible(
102+
4,
103+
ArrayUtils.getLists(newint[][] {{4,1}, {3,2}, {2,4}, {1,3}})),
104+
equalTo(true));
105+
}
37106
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp