Two Fairs (Codeforces 1277E)
Tags: Others, dfs and similar

There are $$$n$$$ cities in Berland and some pairs of them are connected by two-way roads. It is guaranteed that you can pass from any city to any other, moving along the roads. Cities are numerated from $$$1$$$ to $$$n$$$.Two fairs are currently taking place in Berland — they are held in two different cities $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n$$$; $$$a \ne b$$$).Find the number of pairs of cities $$$x$$$ and $$$y$$$ ($$$x \ne a, x \ne b, y \ne a, y \ne b$$$) such that if you go from $$$x$$$ to $$$y$$$ you will have to go through both fairs (the order of visits doesn't matter). Formally, you need to find the number of pairs of cities $$$x,y$$$ such that any path from $$$x$$$ to $$$y$$$ goes through $$$a$$$ and $$$b$$$ (in any order).Print the required number of pairs. The order of two cities in a pair does not matter, that is, the pairs $$$(x,y)$$$ and $$$(y,x)$$$ must be taken into account only once.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 4\cdot10^4$$$) — the number of test cases in the input. Next, $$$t$$$ test cases are specified.The first line of each test case contains four integers $$$n$$$, $$$m$$$, $$$a$$$ and $$$b$$$ ($$$4 \le n \le 2\cdot10^5$$$, $$$n - 1 \le m \le 5\cdot10^5$$$, $$$1 \le a,b \le n$$$, $$$a \ne b$$$) — numbers of cities and roads in Berland and numbers of two cities where fairs are held, respectively.The following $$$m$$$ lines contain descriptions of roads between cities. Each of road description contains a pair of integers $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — numbers of cities connected by the road.Each road is bi-directional and connects two different cities. It is guaranteed that from any city you can pass to any other by roads. There can be more than one road between a pair of cities.The sum of the values of $$$n$$$ for all sets of input data in the test does not exceed $$$2\cdot10^5$$$. The sum of the values of $$$m$$$ for all sets of input data in the test does not exceed $$$5\cdot10^5$$$.

Output: Print $$$t$$$ integers — the answers to the given test cases in the order they are written in the input.


Sample Inputs:
3
7 7 3 5
1 2
2 3
3 4
4 5
5 6
6 7
7 5
4 5 2 3
1 2
2 3
3 4
4 1
4 2
4 3 2 1
1 2
2 3
4 1

Sample Outputs:
4
0
1

Solution (Python):
from collections import defaultdict, deque
from itertools import permutations
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy
MOD = pow(10, 9) + 7
test = int(stdin.readline())
set1 = []
n = 0

def dfs(graph, start, forbidden):
    Stack = [start]
    result = set([])
    visited = [False] * (n + 1)
    while Stack:
        children = Stack.pop()
        for items in graph[children]:
            if items == forbidden or visited[items]:
                continue
            else:
                visited[items] = True
                result.add(items)
                Stack.append(items)
    return result - {start}
for _ in range(test):
    (n, m, a, b) = map(int, stdin.readline().split())
    graph = {}
    for i in range(1, n + 1):
        graph[i] = []
    for i in range(m):
        (u, v) = map(int, stdin.readline().split())
        graph[u].append(v)
        graph[v].append(u)
    result1 = dfs(graph, a, b)
    result2 = dfs(graph, b, a)
    print(len(result1 - result2) * len(result2 - result1))

Solution (Python):
for t in range(int(input())):
    (n, m, a, b) = map(int, input().split())
    neigh_cities = [[] for i in range(n + 1)]
    for i in range(m):
        (x, y) = map(int, input().split())
        neigh_cities[x].append(y)
        neigh_cities[y].append(x)
    with_a = 0
    with_b = 0
    remaining_cities = set(range(1, n + 1))
    remaining_cities.difference_update({a, b})
    while len(remaining_cities) != 0:
        to_be_explored = set()
        already_explored = set()
        connected_to_a = False
        connected_to_b = False
        comp = []
        to_be_explored.add(remaining_cities.pop())
        while len(to_be_explored) != 0:
            city = to_be_explored.pop()
            comp.append(city)
            already_explored.add(city)
            for i in neigh_cities[city]:
                if i == a:
                    connected_to_a = True
                    continue
                if i == b:
                    connected_to_b = True
                    continue
                if i not in already_explored:
                    to_be_explored.add(i)
                    remaining_cities.discard(i)
        if connected_to_a and (not connected_to_b):
            with_a += len(comp)
        if connected_to_b and (not connected_to_a):
            with_b += len(comp)
    print(with_a * with_b)

Solution (Python):
from collections import deque

def solveOne():
    (nVertices, nEdges, v1, v2) = map(int, input().split())
    v1 -= 1
    v2 -= 1
    g = [[] for _ in range(nVertices)]
    for _ in range(nEdges):
        (u, v) = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        g[v].append(u)

    def bfs(start, restricted):
        visited = {start}
        q = deque([start])
        while q:
            v = q.pop()
            for to in g[v]:
                if to != restricted and to not in visited:
                    visited.add(to)
                    q.appendleft(to)
        return visited - {start}
    set1 = bfs(v1, v2)
    set2 = bfs(v2, v1)
    return len(set1 - set2) * len(set2 - set1)
for _ in range(int(input())):
    print(solveOne())