[Timus] Anansi’s Cobweb

Problem statement is here: http://acm.timus.ru/problem.aspx?space=1&num=1671

This is a difficult problem which needs the disjoint set data structure. A vanilla implementation of the disjoint set with the union-find algorithm is not sufficient; one additional insight is required to solve this problem.

Let me explain the problem more directly. A graph is given withN nodes and M edges. How many components are in the graph if q edges are removed? q may vary from 1 to Q and Q may vary from 1 to M.  At every value of q, the number of components have to be returned. To clarify, a component of a graph is a proper subset of nodes of the graph which do not have any edge common with another proper subset of the nodes of the graph.

Now it is easy to see that the problem needs to be solved in reverse order of q. So first of all merge all the edges that are never going to be removed, then start adding the edges that were removed last and count the components. Here is the code:

public class Task1671 {

  // Store the nodes identified by their index.
  private Map<Integer, Node> tree;

  // Number of components in the graph.
  private int count;

  public void solve(int testNumber, InputReader in, OutputWriter out) {
    tree = new HashMap<>();

    int numNodes = in.nextInt();
    int numEdges = in.nextInt();

    Edge[] edges = new Edge[numEdges];
    for (int i = 0; i < numEdges; i++) {
      edges[i] = new Edge(in.nextInt(), in.nextInt());
    }
    int numTears = in.nextInt();
    int[] tearedEdgeNumbers = new int[numTears];

    for (int i = 0; i < numTears; i++) {
      int tear = in.nextInt();
      tearedEdgeNumbers[i] = tear;
      edges[tear - 1].isDeleted = true;
    }

    count = numNodes;

    // First merge all the components that are connected even after removing all the pieces.
    // This becomes the initial set.
    for (int i = 0; i < numEdges; i++) {
      if (!edges[i].isDeleted) {
        union(edges[i]);
      }
    }

    int[] results = new int[numTears];

    // Using the initial set start adding the edges in reverse order of their deletion.
    for (int i = numTears - 1; i >= 0; i--) {
      results[i] = count;
      Edge edge = edges[tearedEdgeNumbers[i] - 1];
      union(edge);
    }

    out.println(results);
  }


  private void union(Edge edge) {
    makeSet(edge);
    Node f1 = tree.get(edge.source);
    Node f2 = tree.get(edge.dest);

    Node p1 = findRep(f1);
    Node p2 = findRep(f2);

    if (p1 == p2) {
      return;
    }

    if (p1.rank >= p2.rank) {
      p2.parent = p1;
      if (p1.rank == p2.rank) {
        p1.rank++;
      }
    } else {
      p1.parent = p2;
    }
    count--;
  }

  private void makeSet(Edge edge) {
    if (!tree.containsKey(edge.source)) {
      makeSet(edge.source);
    }
    if (!tree.containsKey(edge.dest)) {
      makeSet(edge.dest);
    }
  }

  private void makeSet(int data) {
    Node node = new Node();
    node.data = data;
    node.parent = node;
    node.rank = 1;
    tree.put(data, node);
  }

  private Node findRep(Node node) {
    if (node.parent == node) {
      return node;
    }

    return findRep(node.parent);
  }

  class Node {

    int data;
    Node parent;
    int rank;
  }

  class Edge {

    int source;
    int dest;
    boolean isDeleted;

    public Edge(int s, int d) {
      source = s;
      dest = d;
      isDeleted = false;
    }
  }
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.