Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
iama
1332 / 983 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
1

Поиск компонент связности в ориентированом графе

23.08.2011, 14:58. Просмотров 717. Ответов 0
Метки нет (Все метки)

Сабж. Само условие задачи тут.
Мое решение - модифицированый bfs, в булевом массиве head запоминаем вершины, которые "нужно толкать", то есть из которых будут начинаться пути.
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
#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
 
using namespace std;
 
int main()
 {
    vector < vector <int> > g; // граф храним списком ребер
    vector<int>::iterator it;
    queue <int> q;
    bitset <100000> used, head;
    int n, m, i, a, b, c = 0, v;
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    scanf("%d %d", &n, &m);
    g.resize(n);
 
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
 
        a--; b--; // вершины по условию нумеруют с единицы
 
        g[a].push_back(b); // граф ориентированый
    }
 
    for (i = 0; i < n; i++)
        if (!used[i])
        {
            q.push(i);
            dec = 0;
            head[i] = true;
 
            while (!q.empty())
            {
                v = q.front();
                q.pop();
 
                used[v] = true;
 
                for (it = g[v].begin(); it != g[v].end(); it++)
                    if (!used[*it])
                        q.push(*it);
                    else
                        if (head[*it] && *it != i) // присоединяемся к уже посчитаной компоненте, не увеличивая колличества компонент
                            head[*it] = false;
            }
        }
 
    printf("%d\n", head.count());
 
    return 0;
 }
Проходит на всех тестах кроме последнего. Все крайние случаи (полных граф, граф без ребер, разные циклы, дерево, список) протестировал - вроде все нормально.
Помогите найти ошибку

Добавлено через 3 часа 7 минут
Вдруг кому пригодится, контрпример:
Код
4 4
4 3
3 2
2 1
1 2
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2011, 14:58
Ответы с готовыми решениями:

Как найти степень вершины в ориентированом графе?
Как найти степень вершины в ориентированом графе?

Будет ли существовать путь Эйлера в слабо связном ориентированом графе?
Добрый день. Подскажите пожалуйста, в слабо связном ориентированом графе будет ли существовать путь...

Поиск в графе
Здравствуйте, есть следующая задача: Дан массив A длины (n+1), содержащий натуральные числа от 1...

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому существующему ребру...

Поиск путей в графе
Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых множество вершин...

0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2011, 14:58

Поиск циклов в графе
Подскажите, пожалуйста, какие идеи нужно применять к данной задаче

Поиск в ширину в графе
У меня есть небольшая база данных(обычный текстовый файл). Парсирую этот файл и полчается список...

Поиск специфических контуров в графе
Не являюсь специалистом по графам, но возник ряд задач, где их нужно применить. Например, на...


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

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

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