Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Поиск цикла 
:(
    Опции темы
omen666
Дата 18.10.2006, 19:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 6.10.2006

Репутация: нет
Всего: нет



Помогите плз. написать эту программу на С++

const
  maxn = 250;

var
  a: array [1..maxn, 1..maxn] of boolean;
  visited: array [1..maxn] of boolean;
  p: array [1..maxn] of word;
  n: longint;
  cycle: boolean;

procedure init;
var
  i, x, y, nn: longint;
begin
  fillchar(a, sizeof(a), false);
  fillchar(p, sizeof(p), 0);
  fillchar(visited, sizeof(visited), false);
  cycle := false;

  assign(input, 'graph.in');
  reset(input);

  read(n);
  read(nn);

  for i := 1 to nn do
  begin
    read(x, y);
    a[x, y] := true;
    a[y, x] := true;                   
  end;
end;

procedure print;
var
  i, j: integer;
begin
  writeln;
  writeln('number of vertex : ', n);
  writeln('adjacency matrix');
  for i := 1 to n do
  begin
    for j := 1 to n do
      write(ord(a[i, j]));
    writeln;
  end;
end;

procedure dfs(v: longint);
var
  i: integer;
begin
  visited[v] := true;

  for i := 1 to n do
    if a[v, i] then
      if not visited[i] then
      begin
        p[i] := v;
        dfs(i);
      end
      else if p[v] <> i then            
      begin
        cycle := true;
        exit;
      end;
end;

function is_cycle: boolean;
var
  i: longint;
begin
  for i := 1 to n do
    if not visited[i] then
      dfs(i);

  is_cycle := cycle;
end;


begin
  init;

  writeln('depth-first search (cycle)');

  writeln('is cycle : ', is_cycle);
  print;
end.
PM MAIL   Вверх
JackYF
Дата 18.10.2006, 19:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


полуавантюрист
****


Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162



Это не вопрос, а просьба помочь. Обратись в Центр Помощи
Читай правила форума, пожалуйста.


--------------------
Пожаловаться на меня как модератора можно здесь.
PM MAIL Jabber   Вверх
omen666
Дата 18.10.2006, 19:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 6.10.2006

Репутация: нет
Всего: нет



Я это все прекрасно понимаю,но уж очень надо
PM MAIL   Вверх
JackYF
Дата 18.10.2006, 20:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


полуавантюрист
****


Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162



Вот набросок 1-ой части программы...

Код

#include <fstream>

const int maxn = 250;

bool  a[maxn][maxn];
bool  visited[maxn];
unsigned short p[maxn];
long n;
bool cycle;

void init()
{
  long i, x, y, nn;

  std::memset( a, false, sizeof(a) );
  std::memset( p, 0, sizeof(p) );
  std::memset( visited, false, sizeof(visited) );
  cycle = false;

  ifstream input( "graph.in" );  

  input >> n;
  input >> nn;

  for ( int i = 1; i <= nn; ++i )
  {
    input >> x >> y;
    a[x][y] = true;
    a[y][x] = true;                   
  }
}


Добавлено @ 20:17 
Место ifstream поставь там std::ifstream.

Добавлено @ 20:21 
Поехали дальше:

Код

void print()
{
  int i, j;

  std::cout << std::endl;
  std::cout << "number of vertex : " << n;
  std::cout << "adjacency matrix";
  for ( int i = 1; i <= n; ++i )
  {
    for ( int j = 1; j <= n; ++j )
      std::cout << ord( a[i][j] );
    
    std::cout << std::endl;
  }
}


Добавлено @ 20:21 
Что делает функция ord?

Добавлено @ 20:24 
Часть 3:

Код

void dfs( long v );
{
  int i;

  visited[v] = true;

  for ( int i = 1; i <= n; ++i )
    if ( a[v][i] )
      if ( !visited[i] )
      {
        p[i] = v;
        dfs(i);
      }
      else if ( p[v] != i )            
      {
        cycle = true;
        return;
      }
}


Добавлено @ 20:27 
Оставшаяся часть:

Код

bool is_cycle();
{
  long i;

  for ( int i = 1; i <= n; ++i )
    if ( !visited[i] )
      dfs(i);

  is_cycle = cycle;
}


void main()
{
  init();

  std::cout << "depth-first search (cycle)";

  std::cout << "is cycle " << is_cycle() ;
  print();
}


Добавлено @ 20:28 
Пардон, в функции is_cycle

место

Код

is_cycle = cycle;


пиши

Код

return cycle;



--------------------
Пожаловаться на меня как модератора можно здесь.
PM MAIL Jabber   Вверх
omen666
Дата 18.10.2006, 22:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 6.10.2006

Репутация: нет
Всего: нет



Большое тебе спасибо,ты мне очень помог.Респект и уважуха
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »


 




[ Время генерации скрипта: 0.0456 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.