Two Fairs (Codeforces 1276B)
Tags: Others, dsu

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):
import sys
from collections import deque
input = sys.stdin.readline

def Solve(G, a, b):
    visited = [False] * len(G)
    visited[a] = True
    count = 0
    stack = deque()
    for v in G[a]:
        if not visited[v]:
            stack.append(v)
            visited[v] = True
            partial = 0
            inb = False
            while stack:
                vertex = stack.pop()
                partial += 1
                if vertex == b:
                    inb = True
                for item in G[vertex]:
                    if not visited[item]:
                        stack.append(item)
                        visited[item] = True
            if not inb:
                count += partial
    return count
n = int(input())
for _ in range(n):
    (n, m, a, b) = [int(item) for item in input().split()]
    a -= 1
    b -= 1
    G = [[] for _ in range(n)]
    for i in range(m):
        (u, v) = [int(item) - 1 for item in input().split()]
        G[u].append(v)
        G[v].append(u)
    anum = Solve(G, a, b)
    bnum = Solve(G, b, a)
    print(anum * bnum)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

def Solve(G, a, b):
    visited = [False] * len(G)
    visited[a] = True
    count = 0
    stack = deque()
    for v in G[a]:
        if not visited[v]:
            stack.append(v)
            visited[v] = True
            partial = 0
            inb = False
            while stack:
                vertex = stack.pop()
                partial += 1
                if vertex == b:
                    inb = True
                for item in G[vertex]:
                    if not visited[item]:
                        stack.append(item)
                        visited[item] = True
            if not inb:
                count += partial
    return count
n = int(input())
for _ in range(n):
    (n, m, a, b) = [int(item) for item in input().split()]
    a -= 1
    b -= 1
    G = [[] for _ in range(n)]
    for i in range(m):
        (u, v) = [int(item) - 1 for item in input().split()]
        G[u].append(v)
        G[v].append(u)
    anum = Solve(G, a, b)
    bnum = Solve(G, b, a)
    print(anum * bnum)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(6 * 10 ** 5)
input = sys.stdin.readline
INF = 10 ** 9

def dfs(edge, a, b):
    visited = [0] * len(edge)
    visited[a] = 1
    ret = 0
    for item in edge[a]:
        dq = deque()
        if visited[item]:
            continue
        dq.append(item)
        visited[item] = 1
        val = 0
        while dq:
            v = dq.pop()
            val += 1
            if v == b:
                val = -INF
            for nv in edge[v]:
                if not visited[nv]:
                    dq.append(nv)
                    visited[nv] = 1
        if val > 0:
            ret += val
    return ret
n = int(input())
for _ in range(n):
    (n, m, a, b) = [int(item) for item in input().split()]
    a -= 1
    b -= 1
    edge = [[] for _ in range(n)]
    for i in range(m):
        (u, v) = [int(item) - 1 for item in input().split()]
        edge[u].append(v)
        edge[v].append(u)
    anum = dfs(edge, a, b)
    bnum = dfs(edge, b, a)
    print(anum * bnum)