Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Алгоритмы.docx
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
341 Кб
Скачать
☆

45) Задача о домино

Приведём здесь классическую задачу на эйлеров цикл - задачу о домино.

Имеется N доминошек, как известно, на двух концах доминошки записано по одному числу (обычно от 1 до 6, но в нашем случае не важно). Требуется выложить все доминошки в ряд так, чтобы у любых двух соседних доминошек числа, записанные на их общей стороне, совпадали. Доминошки разрешается переворачивать.

Переформулируем задачу. Пусть числа, записанные на донимошках, - вершины графа, а доминошки - рёбра этого графа (каждая доминошка с числами (a,b) - это ребра (a,b) и (b,a)). Тогда наша задача сводится к задаче нахожденияэйлерова пути в этом графе.

int main() {

int n;

vector < vector<int> > g (n, vector<int> (n));

... чтение графа в матрицу смежности ...

vector<int> deg (n);

for (int i=0; i<n; ++i)

for (int j=0; j<n; ++j)

deg[i] += g[i][j];

int first = 0;

while (!deg[first]) ++first;

int v1 = -1, v2 = -1;

bool bad = false;

for (int i=0; i<n; ++i)

if (deg[i] & 1)

if (v1 == -1)

v1 = i;

else if (v2 == -1)

v2 = i;

else

bad = true;

if (v1 != -1)

++g[v1][v2], ++g[v2][v1];

stack<int> st;

st.push (first);

vector<int> res;

while (!st.empty())

{

int v = st.top();

int i;

for (i=0; i<n; ++i)

if (g[v][i])

break;

if (i == n)

{

res.push_back (v);

st.pop();

}

else

{

--g[v][i];

--g[i][v];

st.push (i);

}

}

if (v1 != -1)

for (size_t i=0; i+1<res.size(); ++i)

if (res[i] == v1 && res[i+1] == v2 || res[i] == v2 && res[i+1] == v1)

{

vector<int> res2;

for (size_t j=i+1; j<res.size(); ++j)

res2.push_back (res[j]);

for (size_t j=1; j<=i; ++j)

res2.push_back (res[j]);

res = res2;

break;

}

for (int i=0; i<n; ++i)

for (int j=0; j<n; ++j)

if (g[i][j])

bad = true;

if (bad)

puts ("-1");

else

for (size_t i=0; i<res.size(); ++i)

printf ("%d ", res[i]+1);

}

46) Проверка на ацикличность и нахождение цикла

int n;

vector < vector<int> > g;

vector<char> cl;

vector<int> p;

int cycle_st, cycle_end;

bool dfs (int v) {

cl[v] = 1;

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (cl[to] == 0) {

p[to] = v;

if (dfs (to)) return true;

}

else if (cl[to] == 1) {

cycle_end = v;

cycle_st = to;

return true;

}

}

cl[v] = 2;

return false;

}

int main() {

... чтение графа ...

p.assign (n, -1);

cl.assign (n, 0);

cycle_st = -1;

for (int i=0; i<n; ++i)

if (dfs (i))

break;

if (cycle_st == -1)

puts ("Acyclic");

else {

puts ("Cyclic");

vector<int> cycle;

cycle.push_back (cycle_st);

for (int v=cycle_end; v!=cycle_st; v=p[v])

cycle.push_back (v);

cycle.push_back (cycle_st);

reverse (cycle.begin(), cycle.end());

for (size_t i=0; i<cycle.size(); ++i)

printf ("%d ", cycle[i]+1);

}

}

47) Топологическая сортировка

int n; // число вершин

vector<int> g[MAXN]; // граф

bool used[MAXN];

vector<int> ans;

 

void dfs (int v) {

used[v] = true;

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (!used[to])

dfs (to);

}

ans.push_back (v);

}

 

void topological_sort() {

for (int i=0; i<n; ++i)

used[i] = false;

ans.clear();

for (int i=0; i<n; ++i)

if (!used[i])

dfs (i);

reverse (ans.begin(), ans.end());

}

48)GCD and LCM

int gcd(int a,int b){

//return b ? gcd(b, a % b) : a;

if (b==0)

return a;

else

return gcd(b, a%b);

}

int lcm (int a, int b) {

return a*b / gcd(a, b);

}

Страница 42 | 42