Форум программистов, компьютерный форум CyberForum.ru

Удаление цикла в ориентированном графе - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Пример задания с сайта Яндекса =) http://www.cyberforum.ru/cpp-beginners/thread344254.html
Доброе время суток всем страждущим :jokingly: Просматривая объявления вакансий для программистов не мог не заметить некую шаблонность что-ли, этих самых объявлений. В них говориться что нужен специалист, профессионал. Владение стандартными алгоритмами, знание основных структур данных :D , знание ООП и умение применять его на практике и тд... А кто он ? Этот самый профессионал ? В моем...
C++ Найти следующее после n число, в двоичной записи которого столько же единиц Доброго времени суток. Вопрос в названии темы, полное условие тут. Перебор не проходит. Пробовал #include <iostream> int ones_count(int n){ int res = 0; for( ; n ; n >>= 1) res += n & 1; return res; } http://www.cyberforum.ru/cpp-beginners/thread344236.html
C++ класс дата
Создать класс типа - дата с полями: день (1-31), месяц (1-12), год(целое число).Класс имеет конструктор:с параметрами, без параметров,копирования; деструктор; функции-члены получения дня,месяца и года,а также две функции-члены печати по шаблону: "5 января 1997 года" и "05.01.1997"; функции-члены должны проверять корректность задаваемых параметров. Помогите пожалуйста с определением класса! Вот...
CodeLite - отсутствуют библиотеки C++
Здравствуйте, дорогие форумчане. Необходима кросcплатформенная среда разработки C++. На рабочем компе через центр приложений (Ubuntu) поставил CodeLite. Столкнулся с проблемой отсутствия инклудов windows.h, conio.h и т.д. Проекты просто не запускаются. На домашнем ПК пользуюсь Visual Studio, поэтому с подобной проблемой никогда не сталкивался. В инете манов по это поводу не нашел. Прошу...
C++ Получить список студентов с указанием среднего балла http://www.cyberforum.ru/cpp-beginners/thread344176.html
имеется информация о студентах группы: Ф.И.О., результаты экзаменационной сессии. Мне надо получить список студентов с указанием среднего балла. Для решения данной задачи мне надо использовать массив структур или можно как-то по другому сделать? Если да, то как?
C++ Код ждёт ввода следующей строчки - цикл повторяется бесконечно. В учебнике написано, что вот этот код #include <iostream> #include <string> using namespace std; int main() { string word; while (cin >> word) cout << "прочитано слово: " << word << "\n"; подробнее

Показать сообщение отдельно
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
22.08.2011, 15:26     Удаление цикла в ориентированном графе
Помогите реализовать такой вот алгоритм:
Задан ориентированный граф. Необходимо найти и удалить из него все циклы. Пример графа:
1 2
2 3
2 4
3 1
3 5
4 5
Находим циклы: {1 2 3 1} => Заменяем вершины 2 3 на 1, тем самым получаем граф:
1 1
1 1
1 4
1 1
1 5
4 5
Удаляем дубли и петли:
1 4
1 5
4 5

Реализовать то я его нормально не смог. Вот что вышло:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdlib>
#define SIZE 100
using namespace std;
 
bool graph[SIZE][SIZE];
int cycle[SIZE];
int n,m,k=0;
 
void findcycle(int i);
int main()
{
 int i,a,b,j;
 memset(graph,false,sizeof(graph));
 cin >> n >> m;
 for (i=0; i<m; i++) cin >> a >> b, graph[a][b]=true;
 for (i=1; i<=n; i++)
  {
   k=1;
   cycle[0]=i;
   findcycle(i);
  }
 for (i=1; i<=n; i++)
 for (j=1; j<=n; j++)
  {
   if (graph[i][j]) cout << i << " " << j << endl;
  }
 return 0;
}
 
void findcycle(int i)
{
 int j,l,p,t,q;
 for (j=1; j<=n; j++)
  {
   if (graph[i][j])
    {
     cycle[k]=j;
     k++;
     for (l=0; l<k; l++)
     for (p=l+1; p<k; p++)
      {
       if (cycle[p]==cycle[l])
        {
         cout << cycle[p] << " = " << cycle[l] << endl;
         for (q=0; q<k-1; q++) cout << cycle[q] << " "; cout << cycle[k-1] << endl;
         cout << "p= " << p << endl;
         for (t=l+1; t<=p; t++)
          {
           cout << "Deleting: " << cycle[t-1] << " " << cycle[t] << endl;
           graph[cycle[t-1]][cycle[t]]=false;
           for (q=1; q<k; q++)
            {
             if (graph[cycle[t]][q])
              {
               graph[cycle[t]][q]=false;
               graph[cycle[l]][q]=true;
              }
            }
          }
         return;
        }
      }
     findcycle(j);
    }
  }
}
Помогите реализовать как то
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 20:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru