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

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

Восстановить пароль Регистрация
 
Alex_94
3 / 3 / 1
Регистрация: 21.03.2013
Сообщений: 17
10.07.2013, 22:26     Найти мосты графа #1
Помогите, пожалуйста. В чем ошибка?
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; 
 }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.07.2013, 22:26     Найти мосты графа
Посмотрите здесь:

C++ Найти степени входа и выхода каждой вершины графа.
Построение графа C++
C++ найти количество всех путей и контуров графа длиной S
Найти максимальное и среднее расстояние между центральными вершинами неориентированного графа C++
Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. C++
Найти минимальное расстояние между вершинами 1 и N графа C++
Найти связные компоненты графа C++
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А C++

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

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

Текущее время: 11:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru