Connected Component

connectedcomponent1.png

  • 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.io.InputStreamReader;
      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;
    
              for(int i=1; i<=adjacentList.length-1; i++) {
                  if(checkList[i] == false) {
                      queue.push(i);
                      checkList[i] = true;
    
                      while (!queue.isEmpty()) {
                          int currentVertex = queue.poll();
                          if(adjacentList[currentVertex] != null) {
                              for (int j = 0; j < adjacentList[currentVertex].size(); j++) {
                                  int currentEdge = adjacentList[currentVertex].get(j);
                                  if (checkList[currentEdge] == false) {
                                      queue.add(currentEdge);
                                      checkList[currentEdge] = true;
                                  }
                              }
                          }
                      }
    
                      count++;
                  }
              }
    
              System.out.print(count);
          }
    
          public static void main(String args[]) throws IOException {
              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
              StringTokenizer st = new StringTokenizer(br.readLine());
    
              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++){
                  st = new StringTokenizer(br.readLine());
    
                  int vNum = Integer.parseInt(st.nextToken());
                  int eNum = Integer.parseInt(st.nextToken());
    
                  if(adjacentList[vNum] == null) adjacentList[vNum] = new ArrayList();
                  if(adjacentList[eNum] == null) adjacentList[eNum] = new ArrayList();
    
                  adjacentList[vNum].add(eNum);
                  adjacentList[eNum].add(vNum);
              }
    
              bfs(adjacentList);
          }
      }

Bipartite Graph

BipartiteGraph.png

  • 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)
      3. 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.io.InputStreamReader;
    import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.StringTokenizer;
    
    public class Main {
        public static String bfs(ArrayList<Integer>[] adjacentList){
            ArrayDeque<Integer> queue = new ArrayDeque<>();
            int[] checkList = new int[adjacentList.length];
    
            for(int i=1; i<adjacentList.length; i++) {
                if(checkList[i] == 0) {
                    queue.add(i);
                    checkList[i] = 1;
    
                    while (!queue.isEmpty()) {
                        int currentVertex = queue.poll();
                        if (adjacentList[currentVertex] != null) {
                            for (int j = 0; j < adjacentList[currentVertex].size(); j++) {
                                if (checkList[adjacentList[currentVertex].get(j)] == 0) {
                                    checkList[adjacentList[currentVertex].get(j)] = 3 - checkList[currentVertex];
                                    queue.add(adjacentList[currentVertex].get(j));
                                }
                            }
                        }
                    }
                }
            }
    
            for(int i=1; i<adjacentList.length; i++){
                int vertexColor = checkList[i];
                if(adjacentList[i] != null) {
                    for (int j = 0; j < adjacentList[i].size(); j++) {
                        int edgeColor = checkList[adjacentList[i].get(j)];
                        if(vertexColor != 0 && edgeColor != 0) {
                            if (vertexColor == edgeColor) {
                                return "NO\n";
                            }
                        }
                    }
                }
            }
    
            return "YES\n";
        }
    
        public static void main(String args[]) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuffer sb = new StringBuffer();
            int n = Integer.parseInt(br.readLine());
    
            for(int j=0; j<n; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                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++) {
    
                    st = new StringTokenizer(br.readLine());
    
                    int vNum = Integer.parseInt(st.nextToken());
                    int eNum = Integer.parseInt(st.nextToken());
    
                    if (adjacentList[vNum] == null) adjacentList[vNum] = new ArrayList();
                    if (adjacentList[eNum] == null) adjacentList[eNum] = new ArrayList();
    
                    adjacentList[vNum].add(eNum);
                    adjacentList[eNum].add(vNum);
    
                }
    
                sb = sb.append(bfs(adjacentList));
            }
    
            System.out.print(sb);
    
        }
    }

Permutation Cycle

  • boj.kr/10451
  • find the permutation cycle by searching given permutation
  • it can be solved by DFS