Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

27.04.2011, 23:17. Просмотров 796. Ответов 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 минут
нуу почемууу(
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2011, 23:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Граф.Найти все мосты (C++):

Дан ориентированный граф. Найти все сильно связные компоненты графа - C++
Есть вот такой код, очень прошу исправить под задание в теме поста Спасибо заранее! #include &lt;iostream&gt; #include &lt;vector&gt; ...

Компоненты связности, мосты, точки сочленения - C++
Всем привет! Какими способами можно решить эту задачу? Дано прямоугольное черно-белое изображение размера N x M, которое содержит только...

Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл - C++
помогите очень срочно надо. считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл ...

Найти все четырехзначные числа, у которых все цифры различны - C++
4)Найти все четырехзначные числа, у которых все цифры различны.

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

Найти все четырехзначные числа, у которых все цифры различны - C++
Найти все четырехзначные числа, у которых все цифры различны.

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2011, 23:17
Привет! Вот еще темы с ответами:

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

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

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

Помогите найти ошибку: По двум сторонам и углу найти все остальное - C++
Доброго времени суток. В универе дали задание написать программу &quot;По двум сторонам и углу между ними в треугольнике АВС найти два остальных...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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