Poisonous Graph
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
/* * ============================================================================================ * PROBLEM: Poisonous Graph * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an undirected graph with A nodes and M edges. Assign 1, 2, or 3 to each vertex. * A graph is "Poisonous" if for every edge (u, v), the sum of their values is ODD. * Find the total number of ways to label the graph. Return result modulo 998244353. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Key Insight (Odd Sum Property): * For the sum of two integers to be ODD, one must be EVEN and the other must be ODD. * - Available Numbers: {1, 3} (Odd), {2} (Even). * - Every edge must connect an Odd-labeled vertex to an Even-labeled vertex. * * This property defines a Bipartite Graph. If any connected component contains an ODD cycle, * it cannot be bipartite, and the total ways for the entire graph becomes 0. * * Algorithm: * 1. Identify all connected components using BFS or DFS. * 2. For each component: * a. Check if it is Bipartite using 2-coloring (Color 0 and Color 1). * b. If not Bipartite (odd cycle found), return 0. * c. If Bipartite: * - Let n0 = count of vertices assigned Color 0. * - Let n1 = count of vertices assigned Color 1. * - Case 1: Color 0 gets EVEN (2), Color 1 gets ODD (1 or 3). * Ways = 1^{n0} * 2^{n1} = 2^{n1} * - Case 2: Color 1 gets EVEN (2), Color 0 gets ODD (1 or 3). * Ways = 2^{n0} * 1^{n1} = 2^{n0} * - Total ways for component = (2^{n0} + 2^{n1}) % MOD. * 3. Total ways for the entire graph = Product of ways of all components % MOD. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= A, M <= 3 * 10^5 * MOD = 998244353 * * Time Complexity: * O(A + M) - Linear traversal to find components and perform 2-coloring. * * Space Complexity: * O(A + M) - Adjacency list and color/visited arrays. * * ============================================================================================ / public class PoisonousGraph { public int solve(int A, int[][] edges4) { // TODO: Implement solution return 0; } }