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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Wolfed
2 / 2 / 1
Регистрация: 15.02.2011
Сообщений: 70
#1

Граф.Найти все мосты - C++

27.04.2011, 23:17. Просмотров 780. Ответов 0
Метки нет (Все метки)

Помогите пожалуйста,нужно в графе найти мосты(мост-ребро,при удалении которого увеличивается количество компонент связности) ,у меня следующий вопрос:
как задать входные данные?Ну нужно считывать из файла input.txt,есть два способа - массивом вводить(матричный вид,если ребро между вершинами есть ставим 1) либо структурным(незнаю как, но думаю,что struct list, где каждый List соответсвует вершине,а в поле elem указывать с какими вершинами он соединен ребрами). Вот меня интересует структурный ввод - как его осуществить?Вообще с чем легче работать? Метод решения задачи придумал: Убирать ребро если со всех точек можно добрать до одной из вершин то это не мост,в противном случае мост.

Добавлено через 19 часов 22 минуты
Почему выдает ошибку?( при вводе ошибку выдает(
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
#include <iostream>
#include <vector>
#include <algorithm>
using std::vector;
vector<vector<int>>g;
vector<char>used;
int timer;
vector<int>tin,fup;
int min(int a,int b)
{ if (a>b) return b;
else return a;}
void dfs(int v,int p=-1)
{
    used[v]=true;
    tin[v]=fup[v]=timer++;
    for(size_t i=0;i<g[v].size();++i){
        int to=g[v][i];
        if (to=-p) continue;
        if(used[to])
            fup[v]=min(fup[v],tin[to]);
        else{
            dfs(to,v);
            fup[v]=min(fup[v],fup[to]);
            if(fup[to]>tin[v])
                printf ("%d %d",v,to);
        }
    }
}
int main(){
    int n=6,x,i,j;
FILE *in=fopen("input.txt","r");
for (i=0;i<n;i++)
    for (j=0;j<n;j++)
    {fscanf(in,"%d",&x);
g[i][j]=x;}
timer=0;
used.assign(n,false);
tin.resize(n);
fup.resize(n);
dfs(0);
}
Добавлено через 4 часа 13 минут
нуу почемууу(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2011, 23:17     Граф.Найти все мосты
Посмотрите здесь:

Найти все и вывести все слова в которых есть буква "к" C++
C++ Граф
Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл C++
C++ Граф в С
Найти все столбцы поля, все непрозрачные кубики которых невидимы для наблюдателя, расположенного слева C++
C++ Дается n чисел, нужно вывести сначала все нечетные а затем все четные (найти ошибку)
C++ Найти все трехзначные числа, в которых все цифры различны.
C++ Помогите найти ошибку: По двум сторонам и углу найти все остальное
C++ Найти все такие значения k, что все элементы k-го столбца матрицы содержатся в ее k-ой строке
C++ Найти все четырехзначные числа, у которых все цифры различны
C++ Найти все такие числа k, что k-я строка совпадает с k-м столбцом. Найти наибольший элемент главной диагонали
C++ Найти все четырехзначные числа, у которых все цифры различны

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru