Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
allicenn
0 / 0 / 0
Регистрация: 09.11.2019
Сообщений: 13
1

Как обойти граф, чтобы найти количество связанных компонент? Нужен оптимальный по времени алгоритм

12.02.2020, 16:31. Просмотров 260. Ответов 6

Всем доброго вечера!

Решаю задачу, никак не могу решить, чтобы проходило по времени. Поиск в ширину и глубину пробовала. Ограничения: 1 сек по времени, 128 Мб по памяти.

Надо найти: количество связанных компонент. Например, у графа на этой картинке их 2 https://yadi.sk/i/-T9OL5h8MxJ2Pw.

Формат входных данных (1 строка N от 1 до 105, после N строк с количеством элементов 5*105):

5
a b c
c d e
e h
h
u i a

При таких данных ответ будет 1.

Еще пример:

5
a b c
c d e
e h
h
u i

Тут будет ответ 2.

Что делаю:
1. Считываю построчно, записываю в Map. ключ - номер строки, значение - множество из строки.
2. Перебираю эти данные, ищу связи, записываю в Map.
3. Перебираю Map со связями, далее вызываю стандартный метод с реализацией поиска в ширину (или глубину).

Но всё работает долго. Как еще можно решить задачу? Любой подсказке буду рада Гугл не помогает((


Одно из решений, которое не проходит про времени:

Java
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
import java.io.PrintWriter;
import java.util.*;
 
public class Graph {
    private static Set<Integer> visited = new HashSet<>();
    private static Set<Integer> vertex = new HashSet<>();
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int lines = Integer.valueOf(in.nextLine());
 
        Map<Integer, ArrayList<String>> data = new HashMap<>();
 
        int index = 0;
        while (lines > 0) {
            StringTokenizer st = new StringTokenizer(in.nextLine(), " ");
            ArrayList<String> temp = new ArrayList<>();
            while (st.hasMoreTokens()) {
                temp.add(st.nextToken());
            }
            data.put(index, temp);
            lines--;
            vertex.add(index);
            index++;
        }
 
        Map<Integer, Set<Integer>> map = new HashMap<>();
 
        for (int i = 0; i < data.size(); i++) {
            Set<Integer> set = new HashSet<>();
            for (int j = 0; j < data.size(); j++) {
                if(i != j){
                    for (int k = 0; k < data.get(i).size(); k++) {
                        if(data.get(j).contains(data.get(i).get(k))){
                            set.add(j);
                            break;
                        }
                    }
                }
            }
            map.put(i, set);
        }
 
        int count = 0;
        for (int i = 0; i < map.size(); i++) {
            if(dfs(i, map) == 0){
                count++;
            }
        }
 
        out.println(count);
        out.flush();
    }
 
    private static int dfs(int i, Map<Integer, Set<Integer>> matrix){
        if(visited.contains(i)) return -1;
        visited.add(i);
        vertex.remove(i);
 
        for (int j = 0; j < matrix.size(); j++) {
            if(matrix.get(i).contains(j) && !visited.contains(j)){
                dfs(j, matrix);
            }
        }
        return 0;
    }
}
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.02.2020, 16:31
Ответы с готовыми решениями:

Нужен оптимальный алгоритм умножение битового числа на инверсное ему число
нужен оптимальный алгоритм умножение битового числа на инверсное ему число. допустим 1100011...

Найти минимум в массиве используя наиболее оптимальный алгоритм
Дан массив чисел, надо найти минимум. Препод сказал - дополнительное задание: предложить наиболее...

Как обойти реле времени?
Ситуация: старый немецкий станок. На нем 4 привода. Кнопкой пуск включаются все 4 , но из них 1...


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

Или воспользуйтесь поиском по форуму:
6
KEKCoGEN
Эксперт Java
2287 / 2128 / 543
Регистрация: 28.12.2010
Сообщений: 8,381
13.02.2020, 10:15 2
allicenn, код не читал.

насколько я понимаю, задача решается за O(n).

Берем любую вершину графа и помечаем её как компонент 1. Затем идем от неё ко всем вершинам и помечаем их так же как компонент 1.
Затем идем к следующей вершине. Если она уже помеченна как компонент N, пропускаем, если нет, повторяем предыдущий шаг с новым компонентом.
1
allicenn
0 / 0 / 0
Регистрация: 09.11.2019
Сообщений: 13
13.02.2020, 21:29  [ТС] 3
KEKCoGEN, Да, так и делаю.

Переписала покороче, но всё равно не проходит.
Видимо, что-то еще можно повыкидывать.

Добавлено через 1 час 25 минут
Последняя редакция:

Java
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
import java.io.PrintWriter;
import java.util.*;
public class Graph {
    private static Set<Integer> visited = new HashSet<>();
    private static Set<String> visitedTech = new HashSet<>();
    private static Map<Integer, ArrayList<String>> data = new HashMap<>();
 
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int lines = Integer.valueOf(in.nextLine());
        
        int index = 0;
        while (lines > 0) {
            StringTokenizer st = new StringTokenizer(in.nextLine(), " ");
            ArrayList<String> temp = new ArrayList<>();
            while (st.hasMoreTokens()) {
                temp.add(st.nextToken());
            }
            data.put(index, temp);
            lines--;
            index++;
        }
 
        int count = 0;
 
        for (int i = 0; i < data.size(); i++) {
            if(dfs(i, data.get(i)) == 0){
                count++;
            }
        }
 
        out.println(count);
        out.flush();
    }
 
    private static int dfs(int i, ArrayList<String> list){
        if(visited.contains(i)) {
            return -1;
        }
        visited.add(i);
 
        for (String tech : list) {
            if(!visitedTech.contains(tech)){
                visitedTech.add(tech);
                for (int j = 0; j < data.size(); j++) {
                    if(!visited.contains(j)){
                        if (i != j) {
                            if (data.get(j).contains(tech)) {
                                dfs(j, data.get(j));
                            }
                        }
                    }
                }
            }
        }
        return 0;
    }
}
+ Несколько тестов, но все равно не проходит окончательно(((
0
Aviz__
1211 / 978 / 226
Регистрация: 17.02.2014
Сообщений: 5,224
14.02.2020, 09:49 4
Цитата Сообщение от allicenn Посмотреть сообщение
Например, у графа на этой картинке их 2
какие? картинка показывает два графа. как эти графы описываются в терминах твоей задачи?
так?
a b c f i
a e f
b e f
d h
d g
0
allicenn
0 / 0 / 0
Регистрация: 09.11.2019
Сообщений: 13
14.02.2020, 10:53  [ТС] 5
Цитата Сообщение от Aviz__ Посмотреть сообщение
какие? картинка показывает два графа. как эти графы описываются в терминах твоей задачи?
Да, так. Там нет пути от одного графа к другому, поэтому их 2.

Приведу пример из жизни. В классе 5 человек, у каждого из них есть минимум 1 хобби. Нужно сгруппировать учеников. В группу могут входить дети, у которых есть 1 совпадающее хобби. Минимальная группа - 1 чел (уникальное в классе хобби).

1: рисование, конный спорт
2: рисование
3: хоккей, фигурное катание, прогулки
4: музыкальная школа, рисование
5: бег

Получается 3 группы: (1,2,4), (3), (5)
0
Thousbe
43 / 19 / 7
Регистрация: 04.05.2013
Сообщений: 53
14.02.2020, 11:52 6
Формат входных данных вводит в ступор, какой смысл несет номер строки?

Для сильно ограниченных по времени задач с большим объемом входных данных использовать Scanner нельзя, так как он медленный. Лучше использовать StreamTokenizer. Для определения номера строки есть метод StreamTokenizer.lineno()
0
allicenn
0 / 0 / 0
Регистрация: 09.11.2019
Сообщений: 13
14.02.2020, 11:56  [ТС] 7
Цитата Сообщение от Thousbe Посмотреть сообщение
Формат входных данных вводит в ступор, какой смысл несет номер строки?
Формат входных данных такой:

5
a b c
c d e
e h
h
u i

Хорошо, попробую по-другому считать, спасибо за подсказку!
0
14.02.2020, 11:56
Ответ Создать тему
Опции темы

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