Skip to content

Commit f228e65

Browse files
cod0216cod0216
committed
PS J1707
1 parent 1b92275 commit f228e65

4 files changed

Lines changed: 143 additions & 6 deletions

File tree

‎TIL/J1707_0.java‎

Lines changed: 11 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,8 @@ public static void main(String[] args) throws IOException{
3838

3939
}
4040
for(int i = 1; i<=N; i++) {
41-
DFS(i, color[i]);
41+
// DFS(i, color[i]);
42+
BFS(i, color[i]);
4243
// System.out.println(color[i]);
4344
}
4445

@@ -51,10 +52,11 @@ public static void main(String[] args) throws IOException{
5152
public static void DFS(int node, int num) {
5253
visited[node] = true;
5354
color[node] = num%2;
54-
System.out.println("node = " + node + ", num = " + num);
55+
// System.out.println("node = " + node + ", num = " + num);
5556
for(int i : A[node]) {
5657
if(!visited[i]) {
5758
DFS(i, num+1);
59+
5860
}else {
5961
if(color[i] == (num)%2) {
6062
// System.out.println("node = " + node + ", i = " + i + ", color["+i+"] = "+ color[i] + ", (num+1)%2 = " + (num+1)%2 );
@@ -65,19 +67,22 @@ public static void DFS(int node, int num) {
6567
}
6668
}
6769

68-
public static void BFS(int n) {
70+
public static void BFS(int n, int num) {
6971
Queue<Integer> queue = new LinkedList<>();
7072
queue.add(n);
71-
73+
color[n] = num%2;
7274
while(!queue.isEmpty()) {
7375
int now = queue.poll();
7476
for(int i : A[now]) {
7577
if(!visited[i]) {
78+
color[i] = (color[now] +1)%2;
7679
visited[i] = true;
7780
queue.add(i);
7881
}else {
79-
if(visited[i] == visited[now])
80-
82+
if(color[i] == color[now]) {
83+
check = true;
84+
return;
85+
}
8186
}
8287
}
8388
}

‎TIL/J1717_0.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package TIL;
2+
3+
import java.util.*;
4+
import java.io.*;
5+
6+
public class J1717_0 {
7+
static int[] list;
8+
static boolean check = false;
9+
public static void main(String[] args) throws IOException {
10+
BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
11+
12+
String[] input = buffer.readLine().split(" ");
13+
14+
int n = Integer.parseInt(input[0]);
15+
int m = Integer.parseInt(input[1]);
16+
17+
list = new int[n+1];
18+
19+
for(int i = 0; i<= n; i++) {
20+
list[i] = i;
21+
}
22+
23+
int cnt = 0;
24+
25+
while(cnt != m) {
26+
input = buffer.readLine().split(" ");
27+
int key = Integer.parseInt(input[0]);
28+
int a = Integer.parseInt(input[1]);
29+
int b = Integer.parseInt(input[2]);
30+
check = false;
31+
a = find(a);
32+
b = find(b);
33+
int x = Math.min(a, b);
34+
int y = Math.max(a, b);
35+
36+
if(key == 0) {
37+
union(x, y);
38+
}
39+
else if(key == 1) {
40+
if (x == y) check = true;
41+
if(check) System.out.println("YES");
42+
else System.out.println("NO");
43+
}
44+
45+
cnt++;
46+
}
47+
}
48+
49+
public static void union(int min, int max) {
50+
if (list[max]!= list[min]) list[max] = list[min];
51+
}
52+
53+
public static int find(int num) {
54+
if (list[num] != num)
55+
list[num] = find(list[num]);
56+
57+
return num;
58+
59+
}
60+
}

‎TIL/J2251.java‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package TIL;
2+
3+
import java.util.*;
4+
import java.io.*;
5+
6+
public class J2251 {
7+
static int A, B, C;
8+
static int[] maxCapacity;
9+
static boolean[][] visited;
10+
static boolean[] availableCapicity;
11+
12+
public static void main(String[] args) throws IOException {
13+
BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
14+
15+
String[] input = buffer.readLine().split(" ");
16+
17+
A = Integer.parseInt(input[0]);
18+
B = Integer.parseInt(input[1]);
19+
C = Integer.parseInt(input[2]);
20+
21+
maxCapacity = new int[] {A, B, C};
22+
visited = new boolean[A+1][B+1];
23+
availableCapicity = new boolean[C + 1];
24+
25+
BFS();
26+
for(int i = 0; i < availableCapicity.length; i++) {
27+
if(availableCapicity[i]) System.out.print(i + " ");
28+
}
29+
30+
}
31+
32+
public static void BFS() {
33+
Queue<int[]> queue = new LinkedList<int[]>();
34+
35+
queue.add(new int[] {0, 0, C});
36+
while(!queue.isEmpty()) {
37+
int[] status = queue.poll();
38+
visited[status[0]][status[1]] = true;
39+
40+
if(status[0] == 0) availableCapicity[status[2]] = true;
41+
42+
for(int i = 0; i < 3; i++) {
43+
for(int j = 0; j < 3; j++) {
44+
if(i == j) continue;
45+
int[] newStatus = watering(status, i, j);
46+
if(newStatus != null && !visited[newStatus[0]][newStatus[1]]) {
47+
queue.add(newStatus);
48+
}
49+
}
50+
}
51+
}
52+
53+
}
54+
55+
public static int[] watering(int[] status, int sender, int receiver) {
56+
int residue = maxCapacity[receiver] - status[receiver];
57+
58+
if(residue == 0 || status[sender] == 0 ) return null;
59+
60+
int[] newStatus = status.clone();
61+
if(residue < newStatus[sender]) {
62+
newStatus[sender] -= residue;
63+
newStatus[receiver] += residue;
64+
} else {
65+
newStatus[receiver] += newStatus[sender];
66+
newStatus[sender] = 0;
67+
}
68+
69+
return newStatus;
70+
71+
}
72+
}

‎bin/.DS_Store‎

0 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)