3 / 3 / 1
Регистрация: 21.03.2013
Сообщений: 17
1

Найти мосты графа

10.07.2013, 22:26. Показов 1026. Ответов 0
Метки нет (Все метки)

Помогите, пожалуйста. В чем ошибка?
http://www.e-olimp.com.ua/problems/1943 - условие
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#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; 
 }
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.07.2013, 22:26
Ответы с готовыми решениями:

Мосты графа и реберная связность
Равна ли реберная связность количеству мостов в графе?

Нахождение фактора графа и остова графа для некоторого произвольного графа (5-6 вершин)
Форумчане прошу помощь в выполнение задания по деск. мат. Задание: Нахождение фактора графа и...

Найти все вершины графа, к которым существует путь заданной длины от выделенной вершины графа
Написать программу на prologuse на русском языке как на примере(Определить, является ли связным...

Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа
Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины v1 неориентированного...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.07.2013, 22:26
Помогаю со студенческими работами здесь

wi-fi мосты
добрый день проблемка у меня с передачей изображения с камер по wi-fi мостам два моста которые...

Сгорели мосты
Всем доброго времени суток! У меня проблема. Обьясню все сначало... Начал переустанавливать...

Методы-мосты
Не совсем понял суть методов-мостов. Вот пункт из учебника: Я не понимаю, зачем создается...

диодные мосты
Здравствуйте. Подскажите пожалуйста, можно ли так втыкать в сеть два диодных моста DA3...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru