Jaewoo Song
Jaewoo Song

Categories

  • Tech

Until now, I have thought that I have become accustomed to solving problems clearly with graph searching, for instance, DFS, BFS. But I realized that a problem that doesn’t seem to be solved with a graph can be processed with a graph structure.


https://www.acmicpc.net/problem/15462


First, I thought this problem is similar to function mapping, so I got a correct answer by the following method: if the status of an element stays the same after one phase, then this is passed.

However, the running time was so close to the limit, so I expected that with bigger inputs, this method cannot work.

I referred to one of my alumni and I was surprised that this problem can be handled with the graph’s circulation structure.


If we assume each number as one dot, then the function is an edge, which is a transfer from one spot to another.

So if there is a path from one to the same, we can conclude that there is a cycle that makes one state into the same one eventually.


And a stack can be used to find this circulation structure.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int N;
vector<int> rules;
vector<int> checked;

int main() {

  scanf("%d", &N);

  rules.assign(N+1, 0);
  checked.assign(N+1, 0); // 0: not checked
  for (int i=1; i<=N; ++i) {
    scanf("%d", &rules[i]);
  }

  int count = 0;
  int check_number = 0;

  for (int i=1; i<=N; ++i) {
    if (checked[i] == 0) {
      ++check_number;

      stack<int> s;

      int current = i;
      while(1) {
        if (checked[current] != 0) {
          break;
        }

        s.push(current);
        checked[current] = check_number;
        current = rules[current];
      }

      if (checked[current] == check_number) {
        while(1) {
          int value = s.top();
          s.pop();
          ++count;

          if (current == value) {
            break;
          }
        }
      }
    }
  }

  printf("%d\n", count);

  return 0;
}


Starting from each spot, this algorithm marks the way traveled as one number and pushes that spot to the stack.

Until the spot already marked shows up, it travels the graph pushing all spots into stack marking them as the selected number.

And after meeting a number already marked as the same number, it gets each number from the stack until all nodes are popped up and notes them.

Noted nodes are included in one cycle.

If marked numbers are different, then an additional branch is somewhere therefore we can find that they are not forming a cycle.


This following image is a simple example.

An example of a graph for finding cycle.


If we say that we start from $1$, until we reach $1$->$2$->$3$->$4$->$5$, we check the nodes as the same annotation $a$.

And we return to $3$ again, but this is $3$ which is marked as $a$ so there is a cycle consisting of $3$, $4$, $5$.

After that, $2, 3, 4, 5$ are already checked, so the algorithm ignores them.

It begins with $6$ and it checks $6$->$7$ with a different mark, $b$.

And again we reach $3$ but it already has $a$, so $6$->$7$->$3$ cannot be a cycle.

It is so astonishing that we can find a cycle with this.


And the result after modifying the code…

The result of https://www.acmicpc.net/problem/15462.


It is an amazing time gap between before and after…