Algorithm Study #6 (Graph Problem Solving)

jakeseo_me·2019년 3월 15일
1

목록 보기
18/18

Connected Component

• It is possible that graphs are divided into few pieces
• like this, if graphs are separated, it is called connected component
• There should be path to connect all vertices in each connected component
• Also, there should be no path to connect vertices in other connected components to become a connected component
• Graph above has two of connected component
• to get connected component, we can use BFS or DFS search
• boj.kr/11724
    import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
public static void bfs(ArrayList<Integer>[] adjacentList) {
boolean[] checkList = new boolean[ adjacentList.length + 1 ];
ArrayDeque<Integer> queue = new ArrayDeque<>();
int count = 0;

if(checkList[i] == false) {
queue.push(i);
checkList[i] = true;

while (!queue.isEmpty()) {
int currentVertex = queue.poll();
for (int j = 0; j < adjacentList[currentVertex].size(); j++) {
if (checkList[currentEdge] == false) {
checkList[currentEdge] = true;
}
}
}
}

count++;
}
}

System.out.print(count);
}

public static void main(String args[]) throws IOException {

int numOfVertices = Integer.parseInt(st.nextToken());
int numOfEdges = Integer.parseInt(st.nextToken());

ArrayList<Integer>[] adjacentList = new ArrayList[numOfVertices + 1];

for(int i=0; i<numOfEdges; i++){

int vNum = Integer.parseInt(st.nextToken());
int eNum = Integer.parseInt(st.nextToken());

}

}
}

Bipartite Graph

• If a graph can be divided into A and B like this, it is called Bipartite Graph
• There is no edge among vertices of A (1, 2, 5)
• There is no edge among vertices of B (4, 3, 6)
• every edge's end point is only in A and B
• by using DFS or BFS search, we can check if it is bipartite graph or not
• to check it, we can make the rule for getting it checked.
1. We will paint all the vertices in red or blue
2. after one vertex is painted, the color of paint is switched to opposite color (red | blue)
1. if All vertices are painted it will be over
4. last we have to check if red vertices' edges are all connected with blue vertices
• boj.kr/1707
  import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
ArrayDeque<Integer> queue = new ArrayDeque<>();

if(checkList[i] == 0) {
checkList[i] = 1;

while (!queue.isEmpty()) {
int currentVertex = queue.poll();
for (int j = 0; j < adjacentList[currentVertex].size(); j++) {
}
}
}
}
}
}

int vertexColor = checkList[i];
for (int j = 0; j < adjacentList[i].size(); j++) {
if(vertexColor != 0 && edgeColor != 0) {
if (vertexColor == edgeColor) {
return "NO\n";
}
}
}
}
}

return "YES\n";
}

public static void main(String args[]) throws IOException {
StringBuffer sb = new StringBuffer();

for(int j=0; j<n; j++) {
int numOfVertices = Integer.parseInt(st.nextToken());
int numOfEdges = Integer.parseInt(st.nextToken());
ArrayList<Integer>[] adjacentList = new ArrayList[numOfVertices + 1];

for (int i = 0; i < numOfEdges; i++) {

int vNum = Integer.parseInt(st.nextToken());
int eNum = Integer.parseInt(st.nextToken());

}

}

System.out.print(sb);

}
}

Permutation Cycle

• boj.kr/10451

• find the permutation cycle by searching given permutation

• it can be solved by DFS

• it has only one edge, so it doesn't need to make graph with adjacent matrix

• implementation in java

import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

public static boolean[] checkArr;
public static int[] edgeArr;

public static int dfs(int start){
if(checkArr[start])
return 1;

checkArr[start] = true;
return dfs(edgeArr[start]);
}

public static void main(String args[]) throws IOException {
StringBuffer sb = new StringBuffer();

for(int i=0; i<n; i++){
edgeArr = new int[m+1];
checkArr = new boolean[m+1];

int j=1;
while(st.hasMoreTokens())
edgeArr[j++] = Integer.parseInt(st.nextToken());

int sum = 0;
for(j=1; j<=m; j++)
if(!checkArr[j])
sum += dfs(j);

sb.append(sum + "\n");
}

System.out.print(sb);
}
}

Repeated Progression

• boj.kr/2331
• implementation in java
• the core concept is to find a first number of cycle
  import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {

public static ArrayList<Integer> list = new ArrayList();

public static void main(String args[]) throws IOException {

int a = Integer.parseInt(ap[0]);
int p = Integer.parseInt(ap[1]);
System.out.print(dfs(a, p));

}

public static int dfs(int a, int p){
int apVal = returnAp( a, p );
if( list.contains(apVal) ) {
return list.indexOf(apVal);
}
return dfs(apVal, p);
}

public static int returnAp(int a, int p){
int sum = 0;
while(a > 0){
sum += Math.pow(a % 10, p);
a = a / 10;
}
return sum;
}
}

Term Project

• boj.kr/9466
  import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

public static int[] a;
public static int[] d;
public static int[] s;

public static int dfs(int x, int cnt, int j){
if (d[x] != 0) {
if (j != s[x]) {
return 0;
}
return cnt-d[x];
}
d[x] = cnt;
s[x] = j;
return dfs(a[x], cnt+1, j);
}

public static void main(String args[]) throws IOException {
StringBuffer sb = new StringBuffer();

for(int i=0; i<repeat; i++) {

a = new int[n+1];
d = new int[n+1];
s = new int[n+1];

int index = 1;
while(numbers.hasMoreTokens())
a[index++] = Integer.parseInt(numbers.nextToken());

int ans = 0;
for(int j=1; j<=n; j++) {
if(d[j] == 0){
ans += dfs(j, 1, j);
}
}

sb.append(n-ans + "\n");
}
System.out.print(sb);
}
}
• in this case, i honestly say that i've seen an answer code and my result is not the best so i think it's better to analyze the best answer code.
• the best answer is below.
    import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException {
while (tc-->0){
int mates[] = new int[n];

for (int i = 0; i < n; i++){
mates[i] = new Integer(st.nextToken()) - 1;
}

System.out.println(find(n, mates));
}
}

static int find(int n, int[] mates){
int ans = n;

for (int i = 0; i < n; i++){
int current = i;
current = mates[current];
}

if (links[current] == i + 1){
int start = current;
ans--;
while ((current = mates[current]) != start)
ans--;
}
}
return ans;
}
}

Giving a number to a village

• there is a 2 dimension array
• values which is connected with '1' is considered as a village
• print how many villages in array and the number of 1 in each village
    import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

public static boolean[][] map;

public static void main(String args[]) throws IOException {

map = new boolean[n][n];

for(int x=0; x<n; x++){
for(int y=0; y<n; y++){
if(str.charAt(y) == '1') {
map[x][y] = true;
}
}
}

StringBuffer sb = new StringBuffer();
ArrayList<Integer> al = new ArrayList();
int count = 0;

for(int x=0; x<n; x++){
for(int y=0; y<n; y++){
int xx = lookAround(x, y, n);
if(xx > 0) {
count++;
}
}
}

Collections.sort(al);

for(int i=0; i<al.size(); i++)
sb.append("\n" + al.get(i));

System.out.print(count);
System.out.print(sb);
}

public static int lookAround(int x, int y, int n){
int sum = 0;

if(map[x][y]) {
map[x][y] = false;
if (x - 1 >= 0) {
sum += lookAround(x-1, y, n);
}
if (y - 1 >= 0) {
sum += lookAround(x, y-1, n);
}
if (x + 1 < n) {
sum += lookAround(x+1, y, n);
}
if (y + 1 < n) {
sum += lookAround(x, y+1, n);
}
return 1 + sum;

}else {
return 0;

}
}
}
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. Javascript를 좋아합니다.