Найти, можно ли связать массив строк в круг | Комплект 1

01.01.2020Графы, Строки

По заданному массиву строк найдите, можно ли заданные цепочки объединить в цепочку. Строка X может быть помещена перед другой строкой Y в круге, если последний символ X совпадает с первым символом Y.

Примеры:

Input: arr[] = {"geek", "king"}
Output: Yes, the given strings can be chained.
Note that the last character of first string is same
as first character of second string and vice versa is
also true.

Input: arr[] = {"for", "geek", "rig", "kaf"}
Output: Yes, the given strings can be chained.
The strings can be chained as "for", "rig", "geek" 
and "kaf"

Input: arr[] = {"aab", "bac", "aaa", "cda"}
Output: Yes, the given strings can be chained.
The strings can be chained as "aaa", "aab", "bac" 
and "cda"

Input: arr[] = {"aaa", "bbb", "baa", "aab"};
Output: Yes, the given strings can be chained.
The strings can be chained as "aaa", "aab", "bbb" 
and "baa"

Input: arr[] = {"aaa"};
Output: Yes

Input: arr[] = {"aaa", "bbb"};
Output: No

Input  : arr[] = ["abc", "efg", "cde", "ghi", "ija"]
Output : Yes
These strings can be reordered as, “abc”, “cde”, “efg”,
“ghi”, “ija”

Input : arr[] = [“ijk”, “kji”, “abc”, “cba”]
Output : No

Идея состоит в том, чтобы создать ориентированный граф из всех символов и затем найти, является ли их эйлерова схема в графе или нет.

Графическое представление некоторых строковых массивов приведено на диаграмме ниже,

Если существует эйлерова цепь , то цепь может быть сформирована, иначе нет.
Обратите внимание, что ориентированный граф имеет эйлерову схему только в том случае, если в степени и степени степень каждой вершины одинакова, и все вершины, отличные от нуля, образуют одну сильно связную компоненту.

Ниже приведены подробные шаги алгоритма.

1) Создайте ориентированный граф g с количеством вершин, равным размеру алфавита. Мы создали граф с 26 вершинами в программе ниже.

2) Выполните следующие действия для каждой строки в данном массиве строк.
… ..A) Добавить ребро от первого символа к последнему символу данного графа.

3) Если созданный граф имеет эйлерову схему , вернуть true, иначе вернуть false.

Ниже приведены реализации вышеуказанного алгоритма на C ++ и Python.

C / C ++

// Программа на C ++ для проверки, является ли данный ориентированный граф эйлеровым или нет
#include<iostream>
#include <list>
#define CHARS 26

using namespace std;

// Класс, который представляет неориентированный граф

class Graph

{

int V; // Количество вершин

list<int> *adj; // Динамический массив списков смежности

int *in;

public:

// Конструктор и деструктор

Graph(int V);

~Graph() { delete [] adj; delete [] in; }

// функция для добавления ребра на график

void addEdge(int v, int w) { adj[v].push_back(w); (in[w])++; }

// Метод проверки, является ли этот граф эйлеровым или нет

bool isEulerianCycle();

// Метод проверки, все ли вершины ненулевой степени связаны

bool isSC();

// Функция для создания DFS, начиная с v. Используется в isConnected ();

void DFSUtil(int v, bool visited[]);

Graph getTranspose();

};

Graph::Graph(int V)

{

this->V = V;

adj = new list<int>[V];

in = new int[V];

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

in[i] = 0;

}

/ * Эта функция возвращает true, если ориентированный граф имеет эйлерово

цикл, в противном случае возвращает false * /

bool Graph::isEulerianCycle()

{

// Проверяем, все ли вершины ненулевой степени связаны

if (isSC() == false)

return false;

// Проверяем, одинаковы ли степени в каждой из вершин

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

if (adj[i].size() != in[i])

return false;

return true;

}

// Рекурсивная функция для выполнения DFS, начиная с v

void Graph::DFSUtil(int v, bool visited[])

{

// Пометить текущий узел как посещенный и распечатать его

visited[v] = true;

// Повторение для всех вершин, смежных с этой вершиной

list<int>::iterator i;

for (i = adj[v].begin(); i != adj[v].end(); ++i)

if (!visited[*i])

DFSUtil(*i, visited);

}

// Функция, которая возвращает реверс (или транспонирование) этого графа
// Эта функция нужна в isSC ()
Graph Graph::getTranspose()
{

Graph g(V);

for (int v = 0; v < V; v++)

{

// Повторение для всех вершин, смежных с этой вершиной

list<int>::iterator i;

for(i = adj[v].begin(); i != adj[v].end(); ++i)

{

g.adj[*i].push_back(v);

(g.in[v])++;

}

return g;

}

// Эта функция возвращает true, если все вершины ненулевой степени
// граф сильно связан. Пожалуйста, обратитесь
// https://www.geeksforgeeks.org/connectivity-in-a-directed-graph/amp/

bool Graph::isSC()

{

// Пометить все вершины как не посещенные (для первой DFS)

bool visited[V];

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

visited[i] = false;

// Находим первую вершину с ненулевой степенью

int n;

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

if (adj[n].size() > 0)

break;

// Выполнение обхода DFS, начиная с первой вершины, отличной от нуля.

DFSUtil(n, visited);

// Если обход DFS не посещает все вершины, вернуть false.

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

if (adj[i].size() > 0 && visited[i] == false)

return false;

// Создать перевернутый график

Graph gr = getTranspose();

// Пометить все вершины как не посещенные (для второго DFS)

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

visited[i] = false;

// Делаем DFS для обратного графа, начиная с первой вершины.

// Начинающая вершина должна быть той же отправной точкой первой DFS

gr.DFSUtil(n, visited);

// Если все вершины не посещены во второй DFS, то

// вернуть ложь

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

if (adj[i].size() > 0 && visited[i] == false)

return false;

return true;

}

// Эта функция принимает строку и возвращает true
// если данный массив строк можно связать с
// цикл формы

bool canBeChained(string arr[], int n)

{

// Создать график с ребрами aplha

Graph g(CHARS);

// Создать ребро от первого символа до последнего символа

// каждой строки

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

{

string s = arr[i];

g.addEdge(s[0]-'a', s[s.length()-1]-'a');

}

// данный массив строк можно связать, если

// это эйлеров цикл в созданном графе

return g.isEulerianCycle();

}

// Программа драйвера для проверки вышеуказанных функций

int main()

{

string arr1[] = {"for", "geek", "rig", "kaf"};

int n1 = sizeof(arr1)/sizeof(arr1[0]);

canBeChained(arr1, n1)? cout << "Can be chained n" :

cout << "Can't be chained n";

string arr2[] = {"aab", "abb"};

int n2 = sizeof(arr2)/sizeof(arr2[0]);

canBeChained(arr2, n2)? cout << "Can be chained n" :

cout << "Can't be chained n";

return 0;

}

питон

# Программа Python для проверки, является ли данный ориентированный граф эйлеровым или нет

CHARS = 26

# Класс, представляющий неориентированный граф

class Graph(object):

def __init__(self, V):

self.V = V # Количество вершин

self.adj = [[] for x in xrange(V)] # динамический массив

self.inp = [0] * V

# функция для добавления ребра на график

def addEdge(self, v, w):

self.adj[v].append(w)

self.inp[w]+=1

# Метод проверки, является ли этот граф эйлеровым или нет

def isSC(self):

# Отметить все вершины как не посещенные (для первой DFS)

visited = [False] * self.V

# Найти первую вершину с ненулевой степенью

n = 0

for n in xrange(self.V):

if len(self.adj[n]) > 0:

break

# Выполнить обход DFS, начиная с первой вершины, отличной от нуля.

self.DFSUtil(n, visited)

# Если обход DFS не посещает все вершины, вернуть false.

for i in xrange(self.V):

if len(self.adj[i]) > 0 and visited[i] == False:

return False

# Создать перевернутый график

gr = self.getTranspose()

# Отметить все вершины как не посещенные (для второго DFS)

for i in xrange(self.V):

visited[i] = False

# Делать DFS для обратного графа, начиная с первой вершины.

# Начинающая вершина должна быть той же отправной точкой первой DFS

gr.DFSUtil(n, visited)

# Если все вершины не посещены во второй DFS, то

# вернуть ложь

for i in xrange(self.V):

if len(self.adj[i]) > 0 and visited[i] == False:

return False

return True

# Эта функция возвращает true, если ориентированный граф имеет эйлерово

# цикл, в противном случае возвращает false

def isEulerianCycle(self):

# Проверьте, все ли вершины ненулевой степени связаны

if self.isSC() == False:

return False

# Проверьте, одинаковы ли градусы и степени каждой вершины

for i in xrange(self.V):

if len(self.adj[i]) != self.inp[i]:

return False

return True

# Рекурсивная функция для создания DFS, начиная с v

def DFSUtil(self, v, visited):

# Отметить текущий узел как посещенный и распечатать его

visited[v] = True

# Повторить для всех вершин, смежных с этой вершиной

for i in xrange(len(self.adj[v])):

if not visited[self.adj[v][i]]:

self.DFSUtil(self.adj[v][i], visited)

# Функция, которая возвращает реверс (или транспонирование) этого графа

# Эта функция нужна в isSC ()

def getTranspose(self):

g = Graph(self.V)

for v in xrange(self.V):

# Повторить для всех вершин, смежных с этой вершиной

for i in xrange(len(self.adj[v])):

g.adj[self.adj[v][i]].append(v)

g.inp[v]+=1

return g

# Эта функция принимает строку и возвращает true
# если данный массив строк может быть связан с
# цикл формы

def canBeChained(arr, n):

# Создать график с ребрами 'aplha'

g = Graph(CHARS)

# Создать ребро от первого символа до последнего символа

# каждой строки

for i in xrange(n):

s = arr[i]

g.addEdge(ord(s[0])-ord('a'), ord(s[len(s)-1])-ord('a'))

# Данный массив строк может быть связан, если есть

# - эйлеров цикл в созданном графе

return g.isEulerianCycle()

# Драйверная программа

arr1 = ["for", "geek", "rig", "kaf"]

n1 = len(arr1)

if canBeChained(arr1, n1):

print "Can be chained"

else:

print "Cant be chained"

arr2 = ["aab", "abb"]

n2 = len(arr2)

if canBeChained(arr2, n2):

print "Can be chained"

else:

print "Can't be chained"

# Этот код предоставлен BHAVYA JAIN

Выход:

Can be chained
Can't be chained

Найти, можно ли связать массив строк в круг | Набор 2

Эта статья предоставлена Пиюшем Гуптой . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Найти, можно ли связать массив строк в круг | Комплект 1

0.00 (0%) 0 votes