2019-03-29 OSP

bfs.cpp

// Created by: hashlash
// 2019-03-30
//
// Given G = (V, E)
// V = { v1, v2, v3, ..., vN}
// E = { (e1,f1), (e2,f2), ..., (eM,fM)}
// 
// Traverse using BFS from v1 and output
// the traversal path
//
// Format input:
// N
// v1 v2 v3 .. vN
// M
// e1 f1
// e2 f2
// ...
// eM fM

#include <cstdio>

int N, M;
char v[100];
char adj[128][100];
int adj_size[128];
bool in_queue[128];

char queue[100];
int q_first = 0, q_last = 0;

void bfs_traverse() {
  queue[q_last++] = v[1];
  in_queue[v[1]] = true;

  while (q_first < q_last) {
    char cur_v = queue[q_first++];

    printf("%c ", cur_v);

    for (int i = 0; i < adj_size[cur_v]; i++) {
      char ngh_v = adj[cur_v][i];

      if (!in_queue[ngh_v]) {
        queue[q_last++] = ngh_v;
        in_queue[ngh_v] = true;
      }
    }
  }
  printf("\n");
}

int main() {
  scanf("%d", &N);
  getchar();
  for (int i = 1; i <= N; i++) {
    scanf("%c", &v[i]);
    getchar();
  }

  scanf("%d", &M);
  getchar();
  for (int i = 1; i <= M; i++) {
    char a, b;
    scanf("%c %c", &a, &b);
    getchar();

    adj[a][adj_size[a]++] = b;
    adj[b][adj_size[b]++] = a;
  }

  bfs_traverse();
}

bipartite.cpp

// Created by: hashlash
// 2019-03-30
//
// Given G = (V, E)
// V = { v1, v2, v3, ..., vN}
// E = { (e1,f1), (e2,f2), ..., (eM,fM)}
// 
// Check wether G can be formed as bipartite
// With group `1` and `-1`
//
// Format input:
// N
// v1 v2 v3 .. vN
// M
// e1 f1
// e2 f2
// ...
// eM fM

#include <cstdio>
#include <vector>
using namespace std;

int N, M;
char v[100];
short grp[100];
vector<char> adj[100];

bool gen_bipartite(char cur_v, int cur_grp) {
  grp[cur_v] = cur_grp;

  for (int i = 0; i < adj[cur_v].size(); i++) {
    char ngh_v = adj[cur_v][i];
    if (grp[ngh_v] == cur_grp)
      return false;
  }

  for (int i = 0; i < adj[cur_v].size(); i++) {
    char ngh_v = adj[cur_v][i];
    if (grp[ngh_v] == 0) {
      bool valid = gen_bipartite(ngh_v, -cur_grp);
      if (!valid)
        return false;
    }
  }
  return true;
}

int main() {
  scanf("%d", &N);
  getchar();
  for (int i = 1; i <= N; i++) {
    scanf("%c", &v[i]);
    getchar();
  }
  for (int i = 1; i <= N; i++)
    printf("v[%d] : %c\n", i, v[i]);

  scanf("%d", &M);
  getchar();
  for (int i = 1; i <= M; i++) {
    char a, b;
    scanf("%c %c", &a, &b);
    getchar();

    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  for (int i = 1; i <= N; i++) {
    printf("adj['%c'] => [ ", v[i]);
    for (int j = 0; j < adj[v[i]].size(); j++) {
      printf("'%c' ", adj[v[i]][j]);
    }
    printf("]\n");
  }

  bool is_bipartite = true;
  for (int i = 1; i <= N; i++) {
    if (grp[v[i]] == 0) {
      bool valid = gen_bipartite(v[i], 1);
      if (!valid) {
        is_bipartite = false;
        break;
      }
    }
  }
  printf("%s\n", ((is_bipartite) ? "YA" : "TIDAK"));

  if (is_bipartite) {
    for (int i = 1; i <= N; i++) {
      printf("Group['%c'] -> %d\n", v[i], grp[v[i]]);
    }
  }
}

dijkstra.cpp

// Created by: hashlash
// 2019-03-30
//
// Given G = (V, E)
// V = { v1, v2, v3, ..., vN}
// E = { (e1,f1), (e2,f2), ..., (eM,fM)}
//
// and vertex `source`
// 
// Compute shortest distance from source
// to all vertex in V
//
// Format input:
// N
// v1 v2 v3 .. vN
// M
// e1 f1
// e2 f2
// ...
// eM fM
// source

#include <cstdio>

int N, M;
char v[100];

int w[128][128];
char adj[128][100];
int adj_size[128];

int dist[128];
bool is_labil[128];

bool is_done() {
  for (int i =1; i <= N; i++) {
    char cur_v = v[i];
    if (dist[cur_v] == -1 || is_labil[cur_v])
      return false;
  }
  return true;
}

void dijkstra(char source) {
  dist[source] = 0;

  while (!is_done()) {
    for (int i = 1; i <= N; i++) {
      char cur_v = v[i];

      if (dist[cur_v] != -1 && !is_labil[cur_v]) {
        for (int j = 0; j < adj_size[cur_v]; j++) {
          char ngh_v = adj[cur_v][j];

          if (dist[ngh_v] == -1) {
            dist[ngh_v] = dist[cur_v] + w[cur_v][ngh_v];
            is_labil[ngh_v] = true;

          } else if (is_labil[ngh_v]) {
            int dist_v = dist[cur_v] + w[cur_v][ngh_v];
            if (dist_v < dist[ngh_v])
               dist[ngh_v] = dist_v;
          }
        }
      }
    }

    char min_v = '\0';

    for (int i = 1; i <= N; i++) {
      char cur_v = v[i];

      if (dist[cur_v] != -1 && is_labil[cur_v]){
        if (min_v == '\0' || dist[cur_v] < dist[min_v]) {
          min_v = cur_v;
        }
      }
    }

    is_labil[min_v] = false;
  }
}

int main() {
  scanf("%d", &N);
  getchar();
  for (int i = 1; i <= N; i++) {
    scanf("%c", &v[i]);
    getchar();
  }

  scanf("%d", &M);
  getchar();
  for (int i = 1; i <= M; i++) {
    char a, b;
    int c;
    scanf("%c %c %d", &a, &b, &c);
    getchar();

    adj[a][adj_size[a]++] = b;
    adj[b][adj_size[b]++] = a;

    w[a][b] = w[b][a] = c;
  }

  for (int i = 1; i <= N; i++) {
    dist[v[i]] = -1;
  }

  char source;
  scanf("%c", &source);

  dijkstra(source);

  for (int i = 1; i <= N; i++) {
    printf("Jarak ke `%c' => %d\n", v[i], dist[v[i]]);
  }
}

folder.pas

var
  N, M, Q: integer;
  v: array[1..100] of char;
  parent: array[0..128] of char;

  i: integer;
  a, b, c: char;

function searchable(folder, target: char) : boolean;
begin
  if (parent[ord(folder)] = target) then
  begin
    searchable := true;
  end
  else
  begin
    if (parent[ord(folder)] = folder) then
    begin
      searchable := false;
    end
    else
    begin
      searchable := searchable(parent[ord(folder)], target);
    end
  end
end;

begin
  readln(N);
  for i := 1 to N do
  begin
    read(v[i]);
    parent[ord(v[i])] := v[i];
    read(c);
  end;

  readln(M);
  for i := 1 to M do
  begin
    readln(a, c, b);
    parent[ord(a)] := b;
  end;

  readln(Q);
  for i := 1 to Q do
  begin
    readln(a, c, b);
    if (searchable(a, b)) then
    begin
      writeln('YA');
    end
    else
    begin
      writeln('TIDAK');
    end
  end;
end.

posttest.txt

('2016', 11), >>> logic
('2017', 27),
('2017', 17),
('2017', 18),
('2018', 28),
('2018', 29),
('2018', 30),
('2017', 19),
('2017', 13),
('2017', 5),
('2015', 26),
('2015', 23),
('2015', 24),
('2016', 25),
('2016', 10),
('2018', 25),
('2017', 30),
('2017', 29),
('2016', 8),
('2016', 12),
('2018', 10),
('2015', 15),
('2017', 35),
('2015', 39), >>> ps_code
('2018', 36),
('2016', 27),
('2015', 34),
('2016', 32),
('2015', 46),
('2016', 41),
('2016', 42),
('2015', 36),
('2017', 47), >>> wr_code
('2016', 46),
('2016', 48),