Beautiful Graph (Codeforces 1093D)
Tags: Others, dfs and similar

You are given an undirected unweighted graph consisting of $$$n$$$ vertices and $$$m$$$ edges.You have to write a number on each vertex of the graph. Each number should be $$$1$$$, $$$2$$$ or $$$3$$$. The graph becomes beautiful if for each edge the sum of numbers on vertices connected by this edge is odd.Calculate the number of possible ways to write numbers $$$1$$$, $$$2$$$ and $$$3$$$ on vertices so the graph becomes beautiful. Since this number may be large, print it modulo $$$998244353$$$.Note that you have to write exactly one number on each vertex.The graph does not have any self-loops or multiple edges.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$) — the number of tests in the input.The first line of each test contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5, 0 \le m \le 3 \cdot 10^5$$$) — the number of vertices and the number of edges, respectively. Next $$$m$$$ lines describe edges: $$$i$$$-th line contains two integers $$$u_i$$$, $$$ v_i$$$ ($$$1 \le u_i, v_i \le n; u_i \neq v_i$$$) — indices of vertices connected by $$$i$$$-th edge.It is guaranteed that $$$\sum\limits_{i=1}^{t} n \le 3 \cdot 10^5$$$ and $$$\sum\limits_{i=1}^{t} m \le 3 \cdot 10^5$$$.

Output: For each test print one line, containing one integer — the number of possible ways to write numbers $$$1$$$, $$$2$$$, $$$3$$$ on the vertices of given graph so it becomes beautiful. Since answers may be large, print them modulo $$$998244353$$$.

Note: Possible ways to distribute numbers in the first test:   the vertex $$$1$$$ should contain $$$1$$$, and $$$2$$$ should contain $$$2$$$;  the vertex $$$1$$$ should contain $$$3$$$, and $$$2$$$ should contain $$$2$$$;  the vertex $$$1$$$ should contain $$$2$$$, and $$$2$$$ should contain $$$1$$$;  the vertex $$$1$$$ should contain $$$2$$$, and $$$2$$$ should contain $$$3$$$. In the second test there is no way to distribute numbers.

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

Sample Outputs:
4
0

Solution (Python):
import sys
input = sys.stdin.readline
M = 998244353

def power(a, b):
    r = 1
    while b > 0:
        if b & 1:
            r = r * a % M
        a = a * a % M
        b //= 2
    return r
q = [0] * 300005

def solve():
    mp = {}
    mp.clear()
    (n, m) = map(int, input().split())
    vis = [-1] * (n + 2)
    for _ in range(m):
        (u, v) = map(int, input().split())
        u -= 1
        v -= 1
        if u not in mp:
            mp[u] = []
        if v not in mp:
            mp[v] = []
        mp[u].append(v)
        mp[v].append(u)
    rlt = 1
    for i in range(n):
        cnt = 0
        if i not in mp:
            rlt = rlt * 3 % M
            continue
        if vis[i] == -1:
            vis[i] = 0
            st = 0
            en = 0
            q[en] = i
            en += 1
            while st < en:
                x = q[st]
                if vis[x] == 1:
                    cnt += 1
                st += 1
                for y in mp[x]:
                    if vis[y] == -1:
                        vis[y] = 1 - vis[x]
                        q[en] = y
                        en += 1
                        continue
                    if vis[y] == vis[x]:
                        rlt = 0
            rlt = rlt * (power(2, cnt) + power(2, en - cnt)) % M
    print(rlt)
for _ in range(int(input())):
    solve()

Solution (Python):
from collections import defaultdict, deque
from functools import lru_cache
from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
if type(__builtins__) is not dict or 'profile' not in __builtins__:
    profile = lambda f: f
M = 998244353

@lru_cache(100000)
@profile
def power(b, exp):
    if exp == 0:
        return 1
    if exp == 1:
        return b
    ret = power(b, exp // 2)
    ret = ret * ret
    if exp % 2 != 0:
        ret = ret * b
    return ret % M

@profile
def solve(adj, nodes_remaining, n_nodes):
    ret = 1
    for n in range(1, n_nodes + 1):
        if not nodes_remaining:
            return ret
        if n not in nodes_remaining:
            continue
        colors = {n: False}
        c_f = 1
        c_t = 0
        nodes_remaining.remove(n)
        q = [n]
        while q:
            qn = q.pop()
            n_color = colors[qn]
            for nn in adj[qn]:
                if nn in colors:
                    if colors[nn] == n_color:
                        return 0
                    continue
                colors[nn] = not n_color
                if nn in nodes_remaining:
                    nodes_remaining.remove(nn)
                if colors[nn]:
                    c_t += 1
                else:
                    c_f += 1
                q.append(nn)
        p1 = power(2, c_t)
        p2 = power(2, c_f)
        r = p1 + p2
        if r == 0:
            return 0
        ret *= r
        ret = ret % M
    return ret

def str_to_list_numbers(s):
    return [int(ds) for ds in s.split()]

@profile
def main():
    n_cases = int(input())
    for _ in range(n_cases):
        (n, m) = str_to_list_numbers(input())
        if m == 0:
            print(str(power(3, n)) + '\n')
            continue
        nodes_remaining = set(range(1, n + 1))
        adj = defaultdict(set)
        for _ in range(m):
            (a, b) = str_to_list_numbers(input())
            adj[a].add(b)
            adj[b].add(a)
        s = solve(adj, nodes_remaining, n)
        print(str(s) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque
from functools import lru_cache
from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
if type(__builtins__) is not dict or 'profile' not in __builtins__:
    profile = lambda f: f
M = 998244353

@lru_cache(100000)
@profile
def power(b, exp):
    if exp == 0:
        return 1
    if exp == 1:
        return b
    ret = power(b, exp // 2)
    ret = ret * ret
    if exp % 2 != 0:
        ret = ret * b
    return ret % M

@profile
def solve(adj, nodes_remaining, n_nodes):
    ret = 1
    for n in range(1, n_nodes + 1):
        if not nodes_remaining:
            return ret
        if n not in nodes_remaining:
            continue
        colors = {n: False}
        c_f = 1
        c_t = 0
        nodes_remaining.remove(n)
        q = [n]
        while q:
            qn = q.pop()
            n_color = colors[qn]
            for nn in adj[qn]:
                if nn in colors:
                    if colors[nn] == n_color:
                        return 0
                    continue
                colors[nn] = not n_color
                if nn in nodes_remaining:
                    nodes_remaining.remove(nn)
                if colors[nn]:
                    c_t += 1
                else:
                    c_f += 1
                q.append(nn)
        p1 = power(2, c_t)
        p2 = power(2, c_f)
        r = p1 + p2
        if r == 0:
            return 0
        ret *= r
        ret = ret % M
    return ret

def str_to_list_numbers(s):
    return [int(ds) for ds in s.split()]

@profile
def main():
    n_cases = int(input())
    for _ in range(n_cases):
        (n, m) = str_to_list_numbers(input())
        if m == 0:
            print(str(power(3, n)) + '\n')
            continue
        nodes_remaining = set(range(1, n + 1))
        adj = defaultdict(set)
        for _ in range(m):
            (a, b) = str_to_list_numbers(input())
            adj[a].add(b)
            adj[b].add(a)
        s = solve(adj, nodes_remaining, n)
        print(str(s) + '\n')
if __name__ == '__main__':
    main()