Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.07.2013, 22:28   #1
akademochka
Пользователь
 
Регистрация: 06.11.2011
Сообщений: 44
По умолчанию Найти мосты графа

Помогите, пожалуйста. В чем ошибка?
http://www.e-olimp.com.ua/problems/1943 - условие
Код:
#include <stdio.h>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#pragma comment(linker, "/STACK:20000000");
 typedef vector<int> VInt;
 typedef vector<VInt> VVInt;
 typedef VInt::iterator VIter;
 typedef pair<int, int> PInt;
 typedef vector<PInt> VPInt;
 typedef vector<VPInt> VVPInt;
 typedef VPInt::iterator VPIter;

 VVInt graph;
 VInt colors, parents, enter, leave, low, bcc;
int myTime = 0;
int newIndex = 0;
 set <int> res;
 set<int>::iterator iter;

void visitLow(int u) {
   colors[u] = 1;
   low[u] = enter[u] = ++myTime;
   
   for(VIter it = graph[u].begin(); it != graph[u].end(); it++)
      if(colors[*it] == 0) {
         parents[*it] = u;
         visitLow(*it);
         low[u] = min(low[u], low[*it]);
      } else if(colors[*it] == 1 && *it != parents[u]) {
         low[u] = min(low[u], enter[*it]);
      }
   
   colors[u] = 2;
   leave[u] = ++myTime;      
 }

void visitBCC(int u) {
   for(VIter it = graph[u].begin(); it != graph[u].end(); it++)
      if(parents[*it] == u) {
         bcc[*it] = (low[*it] < enter[u]) ? bcc[u] :         
                    (low[*it] > enter[u]) ? -1 :             
                    (newIndex++);                            
         visitBCC(*it);         
      }
 }

int getBCC(int u, int v) {
    return bcc[(enter[u] > enter[v]) ? u : v];
 }

int main() {
   int n, m, i;

   scanf("%d%d", &n, &m);
   graph.resize(n);
   while(m--) {
      int from, to;
      scanf("%d%d", &from, &to);
      graph[from - 1].push_back(to - 1);
      graph[to - 1].push_back(from - 1);
   }

   colors.assign(n, 0);
   parents.assign(n, -1);
   enter.resize(n);
   leave.resize(n);
   low.resize(n);
   for(i = 0; i < n; i++)
      if(colors[i] == 0)
         visitLow(i);

   bcc.assign(n, -1);
   for(i = 0; i < n; i++)
      if(parents[i] == -1)
         visitBCC(i);   
   

   VPInt bridges;
   VVPInt comps(newIndex);
   for(i = 0; i < n; i++)
      for(VIter it = graph[i].begin(); it != graph[i].end(); it++)
         if(i < *it) {  
            int id = getBCC(i, *it);
           
            if(id == -1)  {bridges.push_back(PInt(i, *it));
            res.insert(*it);
            }
            else {comps[id].push_back(PInt(i, *it));
             }
         }

   printf("%d\n",bridges.size());
   
   printf("%d\n",*res.begin());
    for (iter=res.begin(); iter!=res.end(); )
    {
        iter++;
        if(iter!=res.end())
        printf("%d\n",*iter);
    }
    //printf("\n");

   
    return 0; 
 }
akademochka вне форума Ответить с цитированием
Старый 12.07.2013, 10:04   #2
Kukurudza
Форумчанин
 
Регистрация: 02.06.2011
Сообщений: 282
По умолчанию

Возьмите алгоритм из алголиста
или могу готовый скинуть вечером.
Kukurudza вне форума Ответить с цитированием
Старый 12.07.2013, 17:14   #3
akademochka
Пользователь
 
Регистрация: 06.11.2011
Сообщений: 44
По умолчанию

Алгоритм правильный, просто с выводом номера по порядку ребра, которое является мостом, проблемы
akademochka вне форума Ответить с цитированием
Старый 12.07.2013, 18:41   #4
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,543
По умолчанию

akademochka, а указать проблемную строку - западло? Или нам обязательно ваш код, компилить?
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Старый 14.07.2013, 20:18   #5
akademochka
Пользователь
 
Регистрация: 06.11.2011
Сообщений: 44
По умолчанию

проблемной строки нету, программа работает не правильно
akademochka вне форума Ответить с цитированием
Старый 15.07.2013, 06:57   #6
Kukurudza
Форумчанин
 
Регистрация: 02.06.2011
Сообщений: 282
По умолчанию

возьмите правильный алгоритм:
http://e-maxx.ru/algo/bridge_searching
я им пользуюсь уже года три для задачек академических.
Kukurudza вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Найти диаметр графа. Си. Yakoff Фриланс 4 26.06.2013 10:21
Найти все вершины графа sergei15 Паскаль, Turbo Pascal, PascalABC.NET 0 28.05.2012 19:33
Найти все пути, соединяющие две вершины ориентированного графа. dasterse Помощь студентам 0 13.05.2012 18:38
Раскраска графа (или как найти баг) KANDRAT Помощь студентам 0 07.05.2012 23:44
Найти максимальное независимое множество вершин графа ebozzzavrik Помощь студентам 4 18.05.2011 23:21