{"id":1875,"date":"2020-07-01T09:47:21","date_gmt":"2020-07-01T09:47:21","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1875"},"modified":"2022-03-28T01:17:47","modified_gmt":"2022-03-28T01:17:47","slug":"clan-war","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/clan-war\/","title":{"rendered":"Clan War"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Depth First Search, Disjoint Set<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

There are two clans numbered sequentially from 1<\/code> to N<\/code> and given two integers, u<\/code> and v<\/code> denoting the clan numbers that are fighting each other. We assume that the clans of one nation do not fight each other, they only fight with the clans of the enemy nation. Check whether this assumption is correct or not.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Idea is to seperate clans that fight each other, into two groups. Now we have to check whether any clan fights any clan of the same group, if so our assumption is wrong otherwise it is right.<\/p>\n

There is a graph type which can be applied in this problem, "Biparted Graph"<\/strong>. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets u<\/code> and v<\/code> such that every edge connects a vertex in u<\/code> to one in v<\/code>.<\/p>\n

Now we just have to check whether our graph is biparted or not.
\nBelow we are going to discuss few approaches to solve this problem.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Method 1 :<\/h4>\n
\n

We can assign colours (0<\/code> or 1<\/code>) to determine which group does the vertex belong. We can simply run dfs<\/strong> from a vertex and assign some colour to each new vertex visited. If the parent\u2019s colour is 1, then all its children must be assigned 0. Now if you encounter a visited node having the same colour as it’s parent, the graph isn\u2019t bipartite.<\/p>\n<\/blockquote>\n

Method 2 :<\/h4>\n
\n

Given a graph represented as an adjacency-list (i.e. a list of edges), you can determine if it’s bipartite as follows:<\/p>\n

    \n
  • Initialize a disjoint-set<\/strong> data structure SETS, with a singleton set for each vertex. (If there is an even-length path between two vertices, then we will ultimately unify those two vertices into the same set, unless we return \ua730\u1d00\u029f\ua731\u1d07 first.)<\/li>\n
  • Initialize a parent[ ] for each vertex to \u0274\u026a\u029f. (As we examine edges, we will update parent[ ] for each vertex to one of its neighbors.)<\/li>\n
  • For each edge {u, v}:
    \nIf u and v belong to the same parent in SETS, then return \ua730\u1d00\u029f\ua731\u1d07.<\/li>\n
  • If parent[u] = \u0274\u026a\u029f, set parent[u] := v.
    \nOtherwise, update SETS to unify v with parent[u].<\/li>\n
  • If parent[v] = \u0274\u026a\u029f, set parent[v] := u.
    \nOtherwise, update SETS to unify u with parent[v].<\/li>\n
  • Return \u1d1b\u0280\u1d1c\u1d07.<\/li>\n<\/ul>\n

    Notice that we are returning false as soon as we find a odd length cycle as the odd length cycle can never be divided into two distinct sets. (Think why?).<\/p>\n<\/blockquote>\n

    Algorithms :<\/h3>\n
    \n

    dfs()<\/strong> :<\/h4>\n
      \n
    1. create a queue and push the current vertex now perform following operations untill the queue is empty:<\/li>\n
    2. each time we pop a vertex v<\/code> from queue, ( v<\/code> = queue.front() ), we will mark the vertex v<\/code> as visited (visited[v]= true<\/code>).<\/li>\n
    3. Iterate for all the adjacent vertices of v<\/code> and for every adjacent vertex a<\/code>, do following :\n
        \n
      • if the colour of the vertex is -1<\/code>, then assign the colour opposite to that of v<\/code>.<\/li>\n
      • if the colour of a<\/code> and v<\/code> is same, return false.<\/li>\n
      • if a<\/code> is not visited i.e visited[a]= false<\/code>,
        \nand if a<\/code> has value 1<\/code>. <\/li>\n
      • push the vertex a<\/code> into queue.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<\/blockquote>\n

        Complexity Analysis:<\/h3>\n
        \n

        The time complexity<\/strong> of the first method is represented in the form of O(V+E)<\/code>, where V<\/code> is the number of verices and E<\/code> is the number of edges.<\/p>\n

        The space complexity<\/strong> of the algorithm is O(V)<\/code> for visited[]<\/code> & colour[]<\/code> array.<\/p>\n<\/blockquote>\n

        Solutions:<\/h3>\n

        \t\t\t\t\t\t