Reprezentacje grafów

ra_li.cpp

#include <cstdio>
#include <cstdlib>

#include "timer.h"

int main()
{
  int n, k, x, y, r = 0, mockup = 0;

  srand(time(0));

  scanf("%d %d", &n, &k);

  bool*  GE;

  int* LK;
  int* PK;

  GE = (bool*)calloc(n, sizeof(bool));
  LK = (int*)calloc(k, sizeof(int));
  PK = (int*)calloc(k, sizeof(int));

  for (int i = 0; i < k; i++) {
    scanf("%d %d", &x, &y);

    LK[i] = x;
    PK[i] = y;

    GE[x] = GE[y] = true;
  }

  start_timer();
  for (int i = 0; i < n; i++) {
    if (!GE[i]) continue;
    
    for (int j = 0; j < n; j++) {
      if (!GE[j]) continue;

      for (int z = 0; z < k; z++) {
        if (LK[z] == i && PK[z] == j) {
          mockup++;
          break;
        }
      }

      r++;
    }
  }
  stop_timer("Istnienie krawedzi w liscie incydencji", r);

  free(GE);
  free(LK);
  free(PK);

  return 0;
}

ra_lk.cpp

#include <cstdio>
#include <cstdlib>

#include "timer.h"

using namespace std;

struct node {
  int value;

  node* next;
};

void free_list(node** n) {
  if (*n != NULL) {
    free_list(&((*n)->next));
    free(*n);
  }
}

int main()
{
  int n, k, x, y, r = 0, mockup = 0;
  node* tmp;

  srand(time(0));

  scanf("%d %d", &n, &k);

  bool*  GE;
  node** G;

  GE = (bool*)calloc(n, sizeof(bool));
  G = (node**)calloc(n, sizeof(node*));
  
  for (int i = 0; i < k; i++) {
    scanf("%d %d", &x, &y);

    tmp = (node*)malloc(sizeof(node));
    tmp->value = y;

    if (G[x] == NULL) {
      tmp->next = NULL;
      G[x] = tmp;
    } else {
      tmp->next = G[x];
      G[x] = tmp;
    }

    GE[x] = GE[y] = true;
  }
  
  
  start_timer();
  for (int i = 0; i < n; i++) {
    if (!GE[i]) continue;
    
    for (int j = 0; j < n; j++) {
      if (!GE[j]) continue;

      tmp = G[i];
      while (tmp != NULL) {
        if (tmp->value == j) {
          mockup++;
          break;
        } else {
          tmp = tmp->next;
        }
      }

      r++;
    }
  }
  stop_timer("Istnienie krawedzi w liscie krawedzi", r);

  free(GE);
  for (int i = 0; i < n; i++)
    free_list(&G[i]);
  free(G);

  return 0;
}

ra_mi.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>

#include "timer.h"

int main()
{
  int n, k, x, y, r = 0, mockup = 0;

  srand(time(0));

  scanf("%d %d", &n, &k);

  int** G;
  bool*  GE;

  GE = (bool*)calloc(n, sizeof(bool));
  G = (int**)calloc(n, sizeof(int*));
  for (int i = 0; i < n; i++)
    G[i] = (int*)calloc(k, sizeof(int));

  for (int i = 0; i < k; i++) {
    scanf("%d %d", &x, &y);

    G[x][i] = -1;
    G[y][i] = 1;

    GE[x] = GE[y] = true;
  }

  start_timer();
  for (int i = 0; i < n; i++) {
    if (!GE[i]) continue;
    
    for (int j = 0; j < n; j++) {
      if (!GE[j]) continue;

      for (int z = 0; z < k; z++) {
        if (G[i][z] == -1 && G[j][z] == 1) { mockup++; break; }
      }

      r++;
    }
  }
  stop_timer("Istnienie krawedzi w macierzy incydencji", r);

  free(GE);
  for (int i = 0; i < n; i++)
    free(G[i]);
  free(G);

  return 0;
}

ra_ms.cpp

#include <cstdio>
#include <cstdlib>

#include "timer.h"

int main()
{
  int n, k, x, y, r = 0, mockup = 0;

  srand(time(0));

  scanf("%d %d", &n, &k);

  bool** G;
  bool*  GE;

  GE = (bool*)calloc(n, sizeof(bool));
  G = (bool**)calloc(n, sizeof(bool*));
  for (int i = 0; i < n; i++)
    G[i] = (bool*)calloc(n, sizeof(bool));

  for (int i = 0; i < k; i++) {
    scanf("%d %d", &x, &y);

    G[x][y] = true;
    GE[x] = GE[y] = true;
  }

  start_timer();
  for (int i = 0; i < n; i++) {
    if (!GE[i]) continue;
    
    for (int j = 0; j < n; j++) {
      if (!GE[j]) continue;

      if (G[i][j]) mockup++;
      r++;
    }
  }
  stop_timer("Istnienie krawedzi w macierzy sasiedztwa", r);

  free(GE);
  for (int i = 0; i < n; i++)
    free(G[i]);
  free(G);

  return 0;
}