Перейти к содержимому


LVP

Регистрация: 21 Dec 2011
Offline Активность: Вчера, 10:29 AM
*****

Мои сообщения

В теме: Эйлеров граф

26 January 2020 - 13:57

Автор программы - учащийся 7 класса Гимназии №8 Рубиш Артур

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int g[N][N], n;
vector < int > t;
bool p[N];
void DFS(int v) {
	p[v] = false;
	for (int j = 0; j < n; j++)
    	if (p[j] == true && g[v][j] >= 1)
        	DFS(j);
}
void DFS_E(int v) {
	for (int j = 0; j < n; j++)
    	if (g[v][j] > 0) {
        	g[v][j]--;
        	g[j][v]--;
        	DFS_E(j);
    	}
	t.push_back(v);
}
int main() {
	setlocale(LC_ALL,"RUS");
	cout << "Программа находит в программе эйлеров путь или эйлеров цикл." << endl;
	int m;
	cin >> n >> m;
	for (int i = 0; i < N; i++)
    	for (int j = 0; j < N; j++)
        	g[i][j] = 0;
	for (int i = 0; i < m; i++) {
    	int x, y;
    	cin >> x >> y;
    	x--;
    	y--;
    	g[x][y]++;
    	g[y][x]++;
	}
	for (int i = 0; i < n; i++)
    	p[i] = true;
	int k = 0;
	for (int i = 0; i < n; i++)
    	if (p[i] == true) {
        	cout << i << endl;
        	DFS(i);
        	k++;
    	}
	cout << k << endl;
	if (k > 1)
    	cout << "Что есть в этом графе:ничего,граф-то не связный.";
	else {
    	cout <<"Что есть в этом графе:";
    	int z = 0;
    	for (int i = 0; i < n; i++) {
        	int lol = 0;
        	for (int j = 0; j < n; j++)
            	if (g[i][j] > 0 && i != j)
                	lol += g[i][j];
        	if (lol % 2 == 1)
            	z++;
    	}
    	if (z == 0) {
        	cout << "эйлеров цикл." << endl << "Тут ";
        	DFS_E(0);
        	cout <<t.size() + 1 <<" элементов, и вот они:" << endl;
        	for (int i = 0; i < t.size(); i++)
            	cout << t[i] + 1 << ' ';
    	} else if (z == 2) {
        	cout << "эйлеров путь." << endl << "Тут ";
        	int z1 = 0;
        	for (int i = 0; i < n; i++) {
            	int lol = 0;
            	for (int j = 0; j < n; j++)
                	if (g[i][j] > 0 && i != j)
                    	lol += g[i][j];
            	if (lol % 2 == 1)
                	z++;
            	{
                	g[n][i] = 1;
                	g[i][n] = 1;
                	z1 = i;
            	}
        	}
        	DFS_E(z1);
        	cout << t.size() << " элементов, и вот они:" << endl;
        	for (int i = 0; i < t.size(); i++)
            	cout << t[i] + 1 << ' ';
    	} else
        	cout << "ничего: ни эйлерова цикла, ни эйлерова пути.";
	}
	return 0;
}
//Код для поиска эйлерова пути и эйлерова цикла при любом графе.