Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 3 KB
#include <stdio.h>
#include <stdint.h>
uint8_t elek[1000][1000];
size_t n, e;
int8_t cache_bal[1000][1000], cache_jobb[1000][1000];
int beolvas(void)
{
int a, b;
size_t i, j;
if (scanf("%d %d", &n, &e) != 2) {
printf("hibas bemenet\n");
return 0;
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
elek[i][j] = 0;
for (i = 0; i < e; i++) {
if (scanf("%d %d", &a, &b) != 2) {
printf("hibas bemenet\n");
return 0;
}
elek[a - 1][b - 1] = 1;
elek[b - 1][a - 1] = 1;
}
return 1;
}
int el(int u, int v)
{
return elek[u][v];
}
int mod(int x)
{
if (x < 0)
x += n;
return x % n;
}
void nullaz(void)
{
size_t i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
cache_bal[i][j] = -1;
cache_jobb[i][j] = -1;
}
}
int bal(int u, int v, int szinez);
int jobb(int u, int v, int szinez);
int bal(int u, int v, int szinez)
{
int x, y;
u = mod(u);
v = mod(v);
if (cache_bal[u][v] >= 0 && !szinez)
return cache_bal[u][v];
if (u == v) {
cache_bal[u][v] = 1;
} else {
if (!szinez) {
x = (bal(u, v - 1, 0) && el(v - 1, v));
y = (jobb(v - 1, u, 0) && el(u, v));
if (x) {
cache_bal[u][v] = 66;
} else if (y) {
cache_bal[u][v] = 99;
} else {
cache_bal[u][v] = 0;
}
} else {
switch (cache_bal[u][v]) {
case 66:
elek[mod(v - 1)][v] = 2;
bal(u, v - 1, 1);
break;
case 99:
elek[u][v] = 2;
jobb(v - 1, u, 1);
break;
}
}
}
return cache_bal[u][v];
}
int jobb(int u, int v, int szinez)
{
int x, y;
u = mod(u);
v = mod(v);
if (cache_jobb[u][v] >= 0 && !szinez)
return cache_jobb[u][v];
if (u == v) {
cache_jobb[u][v] = 1;
} else {
if (!szinez) {
x = (jobb(u, v + 1, 0) && el(v + 1, v));
y = (bal(v + 1, u, 0) && el(u, v));
if (x) {
cache_jobb[u][v] = 66;
} else if (y) {
cache_jobb[u][v] = 99;
} else {
cache_jobb[u][v] = 0;
}
} else {
switch (cache_jobb[u][v]) {
case 66:
elek[mod(v + 1)][v] = 2;
jobb(u, v + 1, 1);
break;
case 99:
elek[u][v] = 2;
bal(v + 1, u, 1);
break;
}
}
}
return cache_jobb[u][v];
}
int szamol(int v)
{
int cnt = 0;
size_t i;
for (i = 0; i < n; i++) {
if (elek[i][v] == 2)
cnt++;
if (elek[v][i] == 2)
cnt++;
}
return cnt;
}
void kovetkezo(int v)
{
int i;
printf("%d\n", v + 1);
for (i = 0; i < n; i++)
if (elek[i][v] == 2) {
elek[i][v] = 1;
kovetkezo(i);
return;
}
for (i = 0; i < n; i++)
if (elek[v][i] == 2) {
elek[v][i] = 1;
kovetkezo(i);
return;
}
}
void kiir(void)
{
size_t i;
for (i = 0; i < n; i++)
if (szamol(i) == 1) {
kovetkezo(i);
break;
}
#if 0
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%2d ", elek[i][j]);
printf("\n");
}
#endif
}
void megold(void)
{
size_t i, j;
nullaz();
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
if (bal(i + 1, j, 0) && jobb(i, j, 0)) {
printf("IGEN\n");
bal(i + 1, j, 1);
jobb(i, j, 1);
kiir();
return;
}
}
#if 0
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%2d ", cache_bal[i][j]);
printf("\n");
}
printf("\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%2d ", cache_jobb[i][j]);
printf("\n");
}
#endif
printf("NEM\n");
}
int main(void)
{
if (!beolvas())
return 1;
megold();
return 0;
}
