Задача за граф

[Гост]

Здравейте!
Моля за помощ със задача за граф:
Да се състави функция, която съобщава дали в даден ориентиран граф има върхове от вида

[Гост]

Това направих до момента, но не тръгва
а и не мисля, че отговаря на условието
Моля, помогнете

Код: Избери целия код

#include <iostream>
using namespace std;

const int n = 10;

struct elem
{
   char key;
   elem *next;
}*gr[n];

void init(elem *gr[n]);

void add_node(elem *gr[n],char c);
void add_arc(elem *gr[n],char c1, char c2);
int srch_node(elem *gr[n],char c);
int srch_arc(elem *gr[n], char c1, char c2);
void print_gr();




void init(elem *gr[n])
{

   for (int i = 0; i < n;i++)
      gr[i] = NULL;
}




void add_node(elem *gr[n], char c)
{


   if (!srch_node(gr,c))
   {
      int i = 0;
      while (gr[i] && i < n)
         i++;

      if (gr[i] == NULL)
      {
         gr[i] = new elem;
         gr[i]->key = c;
         gr[i]->next = NULL;
      }
      else
         cout << "nOverflow";
   }
}



void add_arc(elem *gr[n], char c1, char c2)
{


   if (!(srch_arc(gr,c1, c2)))
   {
      if (!(srch_node(gr,c2)))
         add_node(gr,c1);
      if (!srch_node(gr,c2))
         add_node(gr,c2);
      int i = 0;
      while (gr[i] == NULL || gr[i]->key != c1)
         i++;
      elem *p = new elem;
      p->key = c2;
      p->next = gr[i]->next;
      gr[i]->next = p;
   }
}

int srch_node(char c)
{

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

      if (gr[i])

         if (gr[i]->key == c)
            return 1;
   }
   return 0;

}

int srch_arc(elem *gr[n], char c1, char c2)
{

   if (srch_node(gr,c1) && srch_node(gr,c2))
   {
      int i = 0;
      while (gr[i] == NULL || gr[i]->key != c1)
         i++;
      elem *p = gr[i];
      while (p->key != c2 && p->next)
         p = p->next;
      if (p->key == c2)
         return 1;
   }

   return 0;
}

void print_gr()
{

   for (int i = 0; i < n;i++)
      if (gr[i])
      {
         cout << "\nNode:";
         elem *p = gr[i];
         while (p)
         {
            cout << p->key;

            if (p->next)
            {
               cout << " -> ";

            }
            p = p->next;
         }
      }
}



int main()
{
   char c, k;
   int m;
   do
   {
      cout << "\n Main menu \n";
      cout << "\n 1 - Init";
      cout << "\n 2 - Add node";
      cout << "\n 3 - Add arc";
      cout << "\n 4 - Search node";
      cout << "\n 5 - Search arc";
      cout << "\n 6 - Print all";
      cout << "\n 7 - Exit";
      cout << "\n Your choice --> ";
      cin >> m;
      switch (m)
      {
      case 1:
      {
         init(gr);
         break;
      }
      case 2:
      {
         for (int i = 0; i < n; i++)
         {
            cout << "\n Enter node(char): ";
            cin >> c;
            add_node(gr, c);
         }
         break;
      }
      case 3:
      {
         for (int i = 0; i < 5; i++)
         {
            cout << "\n Enter first node (char): ";
            cin >> c;
            cout << "\n Enter second node (char): ";
            cin >> k;
            add_arc(gr, c, k);
         }
         break;
      }
      case 4:
      {
         cout << "\n Enter node (char): ";
         cin >> k;
         if (srch_node(gr, k))
            cout << "\n Search result: Yes!";
         else
            cout << "\n Search result: NO!";
         break;
      }
      case 5:
      {
         cout << "\n Enter first node (char): ";
         cin >> c;
         cout << "\n Enter second node (char): ";
         cin >> k;
         if (srch_arc(gr, c, k))
            cout << "\n Search result: Yes!";
         else
            cout << "\n Search result: NO!";
         break;
      }
      case 6:
      {
         print_gr();
      }
      } // end of switch
   } while (m != 7);
   
   cout << "\n";


   return 0;
}


[peyo]

Здравейте!
Моля за помощ със задача за граф:
Да се състави функция, която съобщава дали в даден ориентиран граф има върхове от вида

От вида на какво?

[Гост]

Обхождане и намиране на всички елементи, които ги има на две места. След това обхождане на така намерените елементи, които имат празен списък от връзки. Ако няма нито един от тях без връзки, или изобщо няма такива с две входящи връзки, значи графа няма елементи от посочения вид.

[peyo]

Ок, това е:

Код: Избери целия код


#include <iostream>
#include <set>
#include <map>
#include <vector>

using namespace std;

typedef map<int, vector<int>> graph_t;

void search(graph_t& graph, int node, set<int> & visited, vector<int>& found) {
   if (visited.find(node) != visited.end()) {
      if (graph[node].size() == 0) {
         found.push_back(node);
      }
   }
   else {
      visited.insert(node);
      for (auto& next_node : graph[node]) {
         search(graph, next_node, visited, found);
      }
   }
}

void main(int argc, char *argv[]) {
   graph_t graph = {
      { 2 , { 0, 3 }},
      { 3 , { 1, 3 }},
      { 0 , { 1, 2 }},
      { 1 , {}},
      { 0 , {4}},
      { 4 , {}},
   };
   
   set<int> visited;
   vector<int> found;
   search(graph, 2, visited, found);
   cout << "Found: ";
   for (auto& node_id : found) {
      cout << node_id << "\n";
   }
}



[Гост]

Това е с STL

[Гост]

Благодаря все пак