бамп

Бамп

Бамп

Бпм

Бамп

Ьампбпм

Ьамп

Ьамп

Ьамп

Ьамп

Ьамп

Ьамп

Ьамп

Все идет к тому, что весь тред будет состоять из моих бампов

Бамп

Бамп

Ьамп

Бамп

Ьамрэп

пмаБ
м
а
Б

Ьаип

Бааамп
а
а
а
м
п

б а а а м п
а
а
а
м
п

п м а б
м
а
б

Бамп

Бамп

У меня еще дохуя времени

Чё-т я не могу в твою задачу въехать.
> 2. Тот же граф, но пара (9, 7). Программа должна вывести 0, т.к. нету такого пути из 9 в 7, чтобы он проходил постоянно по одной и той же вершине(точка сочленения есть, но вершины такой нет, так что можно сказать, что это частный случай).

вершина 1 же сочленение. Или нужно не сочленения всего графа считать, а сочленения графа, получающегося из путей от вершины к вершине?

По сути нужно найти срез между двумя точками, яб гланул алгоритмы те и от них скакал. Удачи.

>>148326731
>Для каждой описанной пары выведите на отдельной строке единственное число --- количество вершин c, таких, что любой путь из ai в bi, проходит через c
Вот вопрос в оригинале. Я сделал вывод, что это точки сочленения.

>>148326731
>а сочленения графа, получающегося из путей от вершины к вершине?
Именно это

>>148326777
Какие алгоритмы?

Ьамп

Уже 30 постов, обсуждение идет полным ходом

>>148327054
Звучит неплохо, но:
Я не указал в ограничение 400 вершин. Работать твой алгоритм будет супер долго, тогда уже лучше завести массив, где будем записывать количество вхождений в эту вершину. Но тут опять же, нужно дохрена раз пускать поиск в глубину, и нужно как то различать пути между собой, короче это не то решение

>>148325445 (OP)
На региональном этапе ВСОШ в этом году было подобное. Жопа моя чует, что нужно сделать некоторое подобие конденсации графа. Вершинами нового графа будут компоненты, на которые распадётся граф при удалении всех точек сочленения (пустые компоненты тоже считаются, т.е. на оппике между 1 и 2 тоже будет компонента) . Рёбрами будут точки сочленения, соединяющие эти компоненты. Думаю, за пару ДФСов это вполне возможно получить.
Дальше тупо находишь флойдом длины путей между каждыми двумя вершинами, и отвечаешь на запросы за О(1).

Особо не вдумывался, мог соврать.

>>148327703
Ты мне сейчас рассказал, как искать точки сочленения. Для этого уже есть алгоритм, лучше ответь мне как путь "вычленить"

>У меня еще дохуя времени
Ну дак сегодня не надо в школу идти

>>148327452
>конденсация
>пустые компоненты
Звучит слишком сложно, я еще не настолько продвинутый. Эту задачу можно решить проще

>>148328063
Эт да))))))))хд

Бамп

Ба п

>>148328145
Не конкретно это точки, а ПУТЬ между ними

ЬамЬ

БАаааааааааа

Бамп

Бамп

Бамп

Бамп

Бамп

Бамп

Бааааааааааааааааааааааааамп

>>148325445 (OP)
КАК ОТКЛЮЧИТЬ ЭТО ГОВНО!!11 АБУ ВЕРНИ ДВАЧ ГЛАЗА КРОВОТОЧАТ СУКА

>>148328701
Брат, как отрубить подскажи, я тебе с дискреткой помогу.

Умеренно аутичный вариант (графы не ебал лет пять) такой: а почему бы тебе не, скажем, взять поиск в глубину; запомнить, какой там путь у тебя нашёлся; а затем попробовать поискать маршруты из точек, соединенных с, скажем, начальной -- и глядеть, что там у тебя в маршрутах. Как только есть маршрут, соединяющий твои А и В без прохода по какой-то точке массиве первичного пути -- эту точку выкидываешь нахуй?

>>148325445 (OP)
import java.io.BufferedReader;
import java.io.InputStream;
import java.util.;

class Pair<T, M> {
private final T first;
private final M second;

// конструктор
private Pair(T value1, M value2) {
this.first = value1;
this.second = value2;
}

// получить первый эл-т пары
public T getFirst() {
return this.first;
}

// получить второй эл-т пары
public M getSecond() {
return this.second;
}

// equals
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;

Pair<?, ?> pair = (Pair<?, ?>) obj;

if (first != null ? !first.equals(pair.first) : pair.first != null) return false;
return !(second != null ? !second.equals(pair.second) : pair.second != null);

}

// hashcode
@Override
public int hashCode() {
int result = first != null ? first.hashCode() : 0;
result = 31 result + (second != null ? second.hashCode() : 0);
return result;
}

// конструктор
public static <T, M> Pair of(T value1, M value2) {
return new Pair(value1, value2);
}
}

class Graph {
private int V; // No. of vertices
private LinkedList<Integer> adj[]; // Array of lists for Adjacency List Representation
int time = 0;
static final int NIL = -1;

// Constructor
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj = new LinkedList();
}

//Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w); // Add w to v's list.
adj[w].add(v); //Add v to w's list
}

// A recursive function that find articulation points using DFS
// u --> The vertex to be visited next
// visited[] --> keeps tract of visited vertices
// disc[] --> Stores discovery times of visited vertices
// parent[] --> Stores parent vertices in DFS tree
// ap[] --> Store articulation points
void APUtil(int u, boolean visited[], int disc[],
int low[], int parent[], boolean ap[]) {

// Count of children in DFS Tree
int children = 0;

// Mark the current node as visited
visited = true;

// Initialize discovery time and low value
disc = low = ++time;

// Go through all vertices adjacent to this
Iterator<Integer> i = adj.iterator();
while (i.hasNext()) {
int v = i.next(); // v is current adjacent of u

// If v is not visited yet, then make it a child of u
// in DFS tree and recur for it
if (!visited[v]) {
children++;
parent[v] = u;
APUtil(v, visited, disc, low, parent, ap);

// Check if the subtree rooted with v has a connection to
// one of the ancestors of u
low = Math.min(low, low[v]);

// u is an articulation point in following cases

// (1) u is root of DFS tree and has two or more chilren.
if (parent == NIL && children > 1)
ap = true;

// (2) If u is not root and low value of one of its child
// is more than discovery value of u.
if (parent != NIL && low[v] >= disc)
ap = true;
}

// Update low value of u for parent function calls.
else if (v != parent)
low = Math.min(low, disc[v]);
}
}

void findCutPoints() {
// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
int disc[] = new int[V];
int low[] = new int[V];
int parent[] = new int[V];
boolean ap[] = new boolean[V]; // To store articulation points

// Initialize parent and visited, and ap(articulation point)
// arrays
for (int i = 0; i < V; i++) {
parent = NIL;
visited = false;
ap = false;
}

// Call the recursive helper function to find articulation
// points in DFS tree rooted with vertex 'i'
for (int i = 0; i < V; i++)
if (visited == false)
APUtil(i, visited, disc, low, parent, ap);

// Now ap[] contains articulation points, print them
for (int i = 0; i < V; i++)
if (ap == true)
System.out.print(i + " ");
}
}

public class Main {

public static void main(String[] args) {
// a set of vertices
Set<Integer> vertices = new HashSet<>();
// a list of edges
List<Pair<Integer, Integer>> edges = new ArrayList<>();
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int start = scanner.nextInt();
int end = scanner.nextInt();
// adding those to the set of vertices
vertices.add(start);
vertices.add(end);
// making a pair, adding it to the list of edges
Pair<Integer, Integer> edge = Pair.of(start, end);
edges.add(edge);
}

Graph graph = new Graph(vertices.size());
for (int i = 0; i < edges.size(); i++) {
int a = edges.get(i).getFirst();
int b = edges.get(i).getSecond();
graph.addEdge(a, b);
}
graph.findCutPoints();
}
}
Вот это говно ищет все точки сочленения в графе, по идее из них можешь вытащить те, которые нужны под конкретную пару вершин. Ну или просто изначально такой подграф на вход давай.А теперь помоги мне избавиться от этого вырвиглазного говна, анончик, я в ахуе блядь, абу совсепм похеал нахуй.

>>148325445 (OP)
>С нахождением точек сочленения проблем нет, но я не знаю, как вычленить из граф
Бля, ты уверен, что правильно хадание понял? Для 7 и 9 будет 0. ЛЮБОЙ путь должен проходить.

http://e-maxx.ru/algo/bridge_searching

>>148325445 (OP)
А, лол так ты это изначально и нашёл. Ебучий зелёный дихайн. Короче, сначала находишь т.очки сочленения, потом удаляешь их из исходного графа и смотришь на свои вершины: если они в одной компоненте связности, то ответ 0, если в разных, то кол-во точек сочл, потому что точка солченения по определению
Пусть вершина v принадлежит некоторым блокам A и B. Вершине v инцидентны некоторые ребра e=uv \in A и f=wv \in B. Ребра e и f находятся в различных блоках, поэтому не существует двух непересекающихся путей между их концами. Учитывая, что один из путей между концами - путь из v в эту же вершину, получаем, что любой путь, соединяющий u и w, пройдет через v. При удалении v между u и w не останется путей, и одна из компонент связности распадется на две.
Типа того. Короче, как-то так. КАК УБРАТЬ ЕБУЧИЙ ЗЕЛЁНЫЙ ДИЗААЙН АААА

Бля чуваки гости пришли, дико извиняюсь, что не могу всем ответить, энивей спасибо, за ваши объяснения