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

Нахождение мостов в графе. - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ С чего начать в изучении C++ http://www.cyberforum.ru/cpp-beginners/thread288923.html
Я решил изучать C++, скиньте мне ссылку на С++ ), в его версиях я не разбираюсь... Поэтому предложите простой вариант! И ещё, какую русскую документацию по C++ посоветуете?
C++ Выделить из IP адреса номер сети и номер узла Здравствуйте. Помогите с задачей Получить в качестве аргумента IP адрес и маску. Выделить из IP адреса номер сети и номер узла. Выяснить входит ли текущий компьютер в заданную сеть. Заранее спасибо. Каждого помощь мне очень важна. Это у меня РГР по программированию http://www.cyberforum.ru/cpp-beginners/thread288916.html
Определение обратной матрицы C++
Помогите, задали в универе написать программку в С++ по определении обратной матрицы, циклический алгоритм
C++ Дерево
Добрый вечер)))) Вот сегодне "изучали "деревья")) Дали задание: "Написать программу копирования вершин, связанных с правым указателем корня дерева в соответствующие вершины «правые вершины»" Я бы прогуглил... но попросту не пойму что от меня требуеться((( (хотя чую, что "лоховское" задание) Можете обьяснить + неотказался бы и от примерчика)))
C++ Буквенно - цифро - знаковый вариант http://www.cyberforum.ru/cpp-beginners/thread288902.html
Помогите плиз разобраца не понимаю в этом ничего Cимволов Буквенно - цифровой вариант Буквенно - цифро - знаковый вариант 6 - RQmBK5 l0?38d
C++ самое длинное слово нужно прокомментировать программу #include <iostream.h> #include <string.h> #include <sstream> #include<conio.h> using namespace std; int main() подробнее

Показать сообщение отдельно
Wolfed
2 / 2 / 1
Регистрация: 15.02.2011
Сообщений: 70
04.05.2011, 22:40     Нахождение мостов в графе.
Дан граф.Найти все мосты.Мост-ребро при удалении которого создается компонента связности(проще говоря если удалить такое ребро,то невозможно будет попасть из одной вершины в ны другую(ну которые соединяло ребро, тоесть если ребро соединяло вершину 1 и вершину 2, то если при удалении из вершины 1 нельзя попасть в вершину 2, то это мост))
входные данные статические, тоесть представлены квадратным массивом размерности NxN,где N количество вершин,если между вершиной N и вершиной M есть ребро, то значение в массиве A[N][M]=1. Если же нет то a[N][m]=0.
Например
0 1 1
1 0 0
1 0 0
Означает что существует ребро между вершинами 1-2,1-3,3-1,3-2.
Предлагаю решить все через рекурсию.
Предлагаю свой алгоритм
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
42
#include <iostream>
#include <vector>
using std::vector;
int g[10][10];
vector<char> used;
int timer;
int tin[10],fup[10];
int min(int a,int b)
{ if(a<b) return a;else return b;}
 
void dfs (int v, int p) {
    int i;
    used[v] = true;
    tin[v] = fup[v] = timer++;
    for (i=0; i<4;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 ("MOST raspolojen mejdy vershinami %d - %d\n",v+1,to+1);
        }
    }
}
 
int main(){
    int n=4,x,i,j;  
FILE *in=fopen("input.txt","r");
for (i=0;i<n;i++)
    for (j=1;j<=n;j++)
    {fscanf(in,"%d",&x);
        g[i][j]=x;
}
fclose(in);
timer=0;
used.assign(n,false);
dfs(0,0);
system("PAUSE");
}
Интересует вопрос,почему высчитывает неправильно, тоесть какую бы я матрицу не вводил то всеравно ответ будет 1 2(
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru