Рубрики

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

По заданному массиву строк найдите, можно ли заданные цепочки объединить в цепочку. Строка 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