Skip to content

Instantly share code, notes, and snippets.

@ruyut
Created June 13, 2019 08:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ruyut/bcca4766805aa0bd85d3b9acb35a77fc to your computer and use it in GitHub Desktop.
Save ruyut/bcca4766805aa0bd85d3b9acb35a77fc to your computer and use it in GitHub Desktop.
#include "pch.h"
#include <iostream>
#include "stdlib.h"
#include "time.h"
#include "string.h"
#define SIZE 7
#define DIM 21
// 0, 1, 2 3 4 5 6
// A, B, C, D, E, F, ERD
char ERD[SIZE][SIZE] = { { 0, 1, 1, 0, 0, 0, 0 },//0
{ 1, 0, 0, 1, 0, 1, 0 },//1
{ 1, 0, 0, 1, 0, 0, 0 },//2
{ 0, 1, 1, 0, 1, 1, 0 },//3
{ 0, 0, 0, 1, 0, 0, 1 },//4
{ 0, 1, 0, 1, 0, 0, 1 },//5
{ 0, 0, 0, 0, 1, 1, 0 } };//6
/*
0:1,2
1:0,3,5
2:0,3
3:1,2,4,5
4:3,6
5:1,3,6
6:4,5
*/
char SEL[SIZE] = { 0, 0, 0, 0, 0, 0, 0 };
char FROM[SIZE];
char level[SIZE] = { 1, 0, 0, 0, 0, 0, 0 };
char ptr[SIZE] = { 0, 0, 0, 0, 0, 0, 0 };
bool cover()
{
for (int i = 0; i < SIZE; i++) if (SEL[i] && level[i] == 0) return false;
return true;
}
void span(int n)
{
for (int j = 0; j < SIZE; j++)if (level[j] == 0)
{
int m = 0;
for (int i = 0; i < SIZE; i++)if (ERD[i][j] && level[i] == n)
{
level[j] = n + 1;
if (rand() % (++m) == 0) ptr[j] = i + 1;
}
}
}
int main()
{
int a = 0, b = 0;
srand(time(NULL)); rand();
scanf("%d %d", &a, &b);
SEL[a] = 1; SEL[b] = 1;
for (int i = 0; i < 10; i++)
{
for (int i = 0; i < SIZE; i++) { FROM[i] = level[i] = ptr[i] = 0; FROM[i] = SEL[i]; }
level[a] = 1;
int n = 1;
while (!cover()) span(n++);
while (n-- > 1)
for (int i = 0; i < SIZE; i++)
if (level[i] == (n + 1) && FROM[i])
FROM[ptr[i] - 1] = true;
printf("FROM\t");
for (int i = 0; i < SIZE; i++)
if (FROM[i])
printf("%d\t", i);
printf("\n");
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment