Note. Added sequentially.
public static int roundUp(int a, int b) {
return (a + b - 1) / b;
}
The calculation is performed using the Euclidean algorithm.
reference: Euclidean algorithm and indefinite equation | Beautiful story of high school mathematics
private static long gcd(long a, long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
For example, if a = 370 b = 273,
Loop | a | b |
---|---|---|
1 | 370 | 273 |
2 | 273 | 370 % 273 = 117 |
3 | 117 | 273 % 117 = 39 |
4 | 39 | 117 % 39 = 0 |
When b = 0, return a
returns the value of a.
That value is the greatest common divisor.
Calculate using the greatest common divisor.
private static long lcm(long a, long b) {
return a * b / gcd(a, b);
}
double rad = Math.toRadians(60);
double ux = (tx-sx)*Math.cos(rad) - (ty-sy)*Math.sin(rad)+sx;
double uy = (tx-sx)*Math.sin(rad) + (ty-sy)*Math.cos(rad)+sy;
Point u = new Point(ux, uy);
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class DFS {
private class Graph {
List<List<Integer>> graph;
boolean[] seen;
public Graph(int n) {
graph = new ArrayList<>();
seen = new boolean[n];
for (int i = 0; i < n; i++) {
graph.add(new ArrayList());
seen[i] = false;
}
}
public void add(int from, int to) {
graph.get(from).add(to);
graph.get(to).add(from);
}
public void search(int v) {
seen[v] = true;
for (int next : graph.get(v)) {
if (seen[next]) continue;
search(next);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int N = sc.nextInt();
final int M = sc.nextInt();
Graph graph = new DFS().new Graph(N);
for (int i = 0; i < M; i++) {
final int A = Integer.valueOf(sc.next());
final int B = Integer.valueOf(sc.next());
graph.add(A, B);
}
graph.search(0);
}
}
Recommended Posts