* 다익스트라
static int Dijkstra(int s, int e) {
PriorityQueue<Node> pq = new PriorityQueye<>();
Arrays.fill(D, Integer.MAX_VALUE);
Node cu = new Node(s, 0);
pq.add(cu);
while(!pq.isEmpty()){
cu = pq.poll;
if(cu.e == e) return cu.c;
for(Node nd : list[cu.e]) {
if(D[nd.e] > cu.c + nd.c) {
D[nd.e] = cu.c + nd.c;
pq.add(new Node(nd.e, (cu.c+nd.c) );
}
}
}
return -1;
}
* 조합 (nCr)
static int nCr(int n, int k) {
if(BI[n][k]>0) return BI[n][k];
else if (k==0 || n==k) return BI[n][k] = 1;
else BI[n][k] = (int)((long)nCr(n-1, k-1) + nCr(n-1, k)) % MOD;
}
* 유클리드호제법(최대공약수)
static int GCD(int a, int b) {
return (b==0)? a: GCD(b, a%b);
}
static int LCM(int a, int b) {
return a*b / GCD(a, b);
}
* 플로이드워셜 (Floyd-Warshall)
static void floydwarshall() {
for(int k==1 ; k<= N ; k++) {
for(int i==1 ; i<= N ; i++) {
for(int j==1 ; j<=N ; j++) {
D[i][j]= Math.min(D[i][j], D[i][k]+D[k][j]);
}
}
}
}
* Union-Find (Dis-Joint Set)
static class DJS {
int[] mom;
DJS(int n){
mom = new int[n+1];
for(int i=1; i<=N ; i++) mom[i] = i;
}
public int find(int n) {
return (mom[n]==n)? n : mom[n] = find(mom[n]);
}
public boolean union(int a, int b) {
a = find(a);
b = find(b);
if(a==b) return false;
mom[b] = a;
return true;
}
}
* Belman-Ford(벨만포드)
static boolean belman(int start){
Arrays.fill(D, Integer.MAX_VALUE);
boolean updated = false;
D[start] = 0;
D[N]=0;
for(int i=1 ; i<=N ; i++){
updated= false;
// 모든간선 검사
for(Node nd : list) {
if(D[nd.s]==Integer.MAX_VALUE) continue;
if(D[nd.e] > D[nd.s] + nd.c) {
D[nd.e] = D[nd.s] + nd.c;
updated = true;
}
}
if(!updated) break;
}
if(updated) return true; // 음의 싸이클.. 존재
else return false;
}
* 위상정렬 (DFS)
static int DFS(int here){
visit[here] = true;
for(Node nd : list[here]){
if(!visit[nd.e])
dfs(nd.e);
}
stack.push(here);
}
* LIS
static int LIS_size(int[] V){
ArrayList<Integer> list = new ArrayList<>();
int tmp = 0;
list.add(tmp);
for(int i = 1; i<=N ; i++) {
if(list.get(list.size()-1) < V[i]){
list.add(V[i]);
continue;
}
tmp = Collections.binarySearch(list, V[i]);
if(tmp < 0) list.set(-tmp-1, V[i]);
}
return list.size()-1;
}
* ACL(최저 공통조상)
// 부모 관계 초기화
static void bfs(int here) {
Queue<Node> qu = new ArrayDeque<>();
Node cu = new Node(here, 0);
qu.add(cu);
while(!qu.isEmpty()){
cu = qu.poll;
if(visited[cu.e]) continue;
vistied[cu.e] = true;
Dep[cu.e] = cu.c;
for(int nd : VT[cu.e]){
if(!visite[nd]){
Par[nd][0] = cu.e;
qu.add(new Node(nd, cu.c+1);
}
}
}
}
static void find() {
for(int j=1 ; j<21 ; j++) {
for(int i==1 ; i<= N ; i++) {
Par[i][j] = Par[Par[i][j-1]][j-1];
}
}
}
static int LCA(int x, int y) {
if (Dep[x] > Dep[y]) {
int tmp = y;
y = x;
x = tmp;
}
for(int i = 20 ; i >= 0 ; i--) {
if(Dep[y] - Dep[x] >= (1 << i))
y = Par[y][i];
}
if(x==y) return x;
for(int i=20 ; i>= 0 ; i--) {
if(Par[x][i]!=Par[y][i]){
x = Par[x][i];
y = Par[y][i];
}
}
return Par[x][0];
}
* Index Search
// Tree Depth size == Array 중간값
static int starIdx() {
int ret = 1;
for(ret=1 ; ret<=N ; ret*=2) ;
return ret;
}
static void treeInit(int startIdx) {
for(int i=startIdx ; i > 0 ; i--){
Tree[i] = Tree[2*i] + Tree[2*i+1];
}
}
static void update(int h, int v) { // h 는 startIdx가 더해진 값.
Tree[h] = v;
h/=2;
for(int i=h ; i>0 ; i--) {
Tree[i] = Tree[2*i] + Tree[2*i+1];
}
}
static int query(int a, int b) {
int result = 0;
while(a<=b){
// 시작하는 부분이 홀수인지 판단합니다.
if ((a & 1) == 1) {
sum += Tree[a];
a++;
}
// 끝나는 부분이 짝수인지 판단합니다.
if ((b & 1) == 0) {
sum += tree[b];
b--;
}
a /= 2;
b /= 2;
}
// 밑에서부터 시작과 끝이 올라와서 만나게 된다면 그 구간은 현재 노드가 같은 부모인 것이고,
// 현재 노드는 하위 모든 노드들의 합을 나타내는 것입니다.
if (a == b)
sum += tree[a];
return sum;
}
*Prime (소수)
static void Prime() {
for(int i=1 ; i <= 1000000 ; i++} {
Prime[i] = true;
for(int j=2 ; j*j <= i ; j++) {
if(i%j == 0)
Prime[i] = false;
break;
}
}
}
* 단절점
static int DFS(int here, int dep, boolean root){
D[here] = dep;
int ret = D[here];
int child = 0;
for(int next : VT[here]) {
if(D[next] == 0) {
child++;
int df = DFS(next, dep+1, false);
if(!root && df >= D[here] ) C[here]=false;
ret = Math.min(ret, df);
} else {
ret = Math.min(ret, D[next]);
}
}
if(root && child >= 2) C[here] = true;
return ret;
}
* 누적합(펜윅트리)
static void update(int h, int v) {
for(int i=h ; i <= N ; i+=(i&-1)) PT[i] += v;
}
static long query(int h) {
long result = 0;
for(int i=h ; i > 0 ; i-=(i&-i)) result+=PV[i];
return result;
}