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

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

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

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

27.04.2011, 23:17. Просмотров 784. Ответов 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     Граф.Найти все мосты
Посмотрите здесь:

Найти все такие значения k, что все элементы k-го столбца матрицы содержатся в ее k-ой строке - C++
Hайти все такие значения k, что все элементы k-го столбца матрицы содержатся в ее k-ой строке.

Дается n чисел, нужно вывести сначала все нечетные а затем все четные (найти ошибку) - C++
Дается n чисел, нужно вывести сначала все нечетные а затем все четные, я написал но на втором тесте прога запарывается #include...

Найти все столбцы поля, все непрозрачные кубики которых невидимы для наблюдателя, расположенного слева - C++
Поле размером NxM заполнено прозрачными и непрозрачными кубиками. Найти все столбцы поля, все непрозрачные кубики которых невидимы для...

Найти все и вывести все слова в которых есть буква "к" - C++
дана строка (ввод с клавы) найти все и вывести все слова в которых есть буква &quot;к&quot;!!!!!!!!!!!!!!!!!!!!!!(разделители между словами точка или...

Найти все такие числа k, что k-я строка совпадает с k-м столбцом. Найти наибольший элемент главной диагонали - C++
Найти все такие числа k, что k-я строка совпадает с k-м столбцом. Найти наибольший элемент главной диагонали матрицы и вывести на печать...

Покрашенный граф - C++
Привет для вот такого условия Дан ориентированный граф, у которого каждая дуга покрашена в один из трех цветов. Требуется найти длину...

Вроде бы граф - C++
Как делается эта задачка? Сделайте пожалуйста, кто может.. Спасибо ! Дан прямоугольник MxN. Найти все варианты как можно добраться из...

Граф - WxDev C++ - C++
Добрый вечер. Вот код графа, Писал сам. По логике вроде всё должно как бы работать. Но Выкидывает пару ошибок насчет нехватки {; Может...

Неориентированный граф!!! - C++
Еще раз обращаюсь за помощью к форуму..от этих задач зависит стипендия! Помогите пожалуйста! Задача 1. Для неориентированного графа...

Двудольный граф?? - C++
Проверка является ли граф двудольным))


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

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

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