یک گراف سادهی همبند n n راسی به شما داده است. در ابتدا رنگ تمامی راسها به جز دو راس r…
- User
یک گراف سادهی همبند n n راسی به شما داده است. در ابتدا رنگ تمامی راسها به جز دو راس r r و b b، سفید است. راس r r قرمز رنگ است و یک مهرهی قرمز نیز روی آن وجود دارد. راس b b سیاه رنگ است و یک مهرهی سیاه روی آن وجود دارد.
در هر ثانیه به صورت تصادفی یکی از دو رنگ سیاه و قرمز انتخاب میشود و به ازای هر مهره از رنگ انتخاب شده، که برای مثال در راس v v قرار دارد، در تمامی راسهای همسایه راس v v در گراف یک مهرهی جدید از همان رنگ قرار داده میشود. اگر راسی که مهرهی جدید در آن قرار میگیرد سفید باشد، رنگ راس به رنگ آن مهره در خواهد آمد و در غیراینصورت رنگ راس تغییر نخواهد کرد.
راسهای گراف در انتهای این عملیات، یعنی زمانی که تمامی راسها رنگ شدهاند، چند رنگآمیزی متفاوت میتوانند داشته باشند؟ دو رنگ آمیزی متفاوت اند اگر رنگ یک راس در آن دو رنگآمیزی متفاوت باشد.
ورودی در خط اول ورودی چهار عدد طبیعی n n و m m و r r و b b، به ترتیب تعداد راسهای گراف، تعداد یالهای گراف، شمارهی راس r r و شمارهی راس b b، آمده است. در هر یک از m m خط بعدی دو عدد طبیعی v i v i و u i u i آمدهاست که نشاندهندهی وجود یک یال بین دو راس v i v i و u i u i در گراف است. گراف داده شده ساده و همبند است. 2 ≤ n ≤ 100
000 2≤n≤100 000 1 ≤ m ≤ m i n ( ( n 2 ) , 200
000 ) 1≤m≤min(( 2 n ),200 000) 1 ≤ r , b ≤ n 1≤r,b≤n r ≠ b r =b 1 ≤ v i , u i ≤ n 1≤v i ,u i ≤n
خروجی در تنها خط خروجی باقیماندهی تعداد رنگآمیزیهای متفاوت گراف در انتهای عملیات بر 1 0 9 + 7 10 9 +7 را چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۱۷ n ≤ 20 n≤20 ۲ ۲۶ n ≤ 1
000 n≤1 000 ۳ ۵۷ بدون محدودیت اضافی مثال ورودی نمونه ۱ 4 3 2 3 1 2 2 3 3 4 Plain text خروجی نمونه ۱ 3 Plain text ورودی نمونه ۲ 6 6 1 6 1 2 2 3 2 4 3 5 4 5 5 6 Plain text خروجی نمونه ۲ 4 Plain text ورودی نمونه ۳ 8 9 1 2 1 3 3 2 1 4 4 5 5 2 1 6 6 7 7 8 8 2 Plain text خروجی نمونه ۳ 8 java
- Assistant
To solve this problem, we need to determine the number of distinct colorings of the graph under the given constraints. Here's a step-by-step explanation of how to approach the problem:
Understanding the Problem
- Graph Structure: You are given a connected graph with
nvertices andmedges. Two specific vertices,randb, are initially colored red and black, respectively. All other vertices start as white. - Color Spreading Mechanism: At each step, one of the two colors (red or black) is randomly selected. All pieces of the chosen color spread to their adjacent (neighboring) vertices. If a vertex is white, it adopts the new color; otherwise, its color remains unchanged.
- Final Coloring: The process continues until all vertices are colored. We need to count the number of possible distinct final colorings.
Key Insight
The final color of each vertex depends on which color reaches it first. Here's how to determine the possible colorings:
- Connected Components After Removing
randb: Remove the two specific verticesrandbfrom the graph. Letcbe the number of connected components remaining. - Direct Connection Between
randb:- If
randbare directly connected by an edge: The number of distinct colorings is2^c - 1. - If
randbare not directly connected: The number of distinct colorings is2^c.
- If
This formula is derived based on how the colors can spread independently across the connected components after removing
randb.Calculation Steps
- Check for Direct Edge: Determine if there is a direct edge between
randb. - Find Connected Components: Remove
randbfrom the graph and count the number of connected componentsc. - Apply the Formula:
- If
randbare directly connected, the number of colorings is2^c - 1. - Otherwise, it is
2^c.
- If
Example Walkthrough
- Sample Input 1:
4 3 2 3 1 2 2 3 3 4- After removing vertices
2and3, there are 2 connected components:{1}and{4}. randbare directly connected.- Number of colorings:
2^2 - 1 = 3.
- After removing vertices
Final Implementation
The solution involves using BFS to count connected components after removing
randband then applying the formula based on whetherrandbare directly connected.Here’s the Java implementation:
import java.util.*; import java.io.*; public class Main { static int n, m, r, b; static ArrayList<ArrayList<Integer>> adj; static boolean[] removed; static boolean[] visited; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().split(" "); n = Integer.parseInt(first[0]); m = Integer.parseInt(first[1]); r = Integer.parseInt(first[2]); b = Integer.parseInt(first[3]); adj = new ArrayList<>(); for(int i=0;i<=n;i++) adj.add(new ArrayList<>()); boolean directEdge = false; for(int i=0;i<m;i++){ String[] edge = br.readLine().split(" "); int u = Integer.parseInt(edge[0]); int v = Integer.parseInt(edge[1]); adj.get(u).add(v); adj.get(v).add(u); if( (u == r && v == b) || (u == b && v == r)) { directEdge = true; } } removed = new boolean[n+1]; removed[r] = true; removed[b] = true; visited = new boolean[n+1]; int components =0; for(int i=1;i<=n;i++) { if(!removed[i] && !visited[i]){ components++; bfs(i); } } long MOD = 1000000007; long result; if(directEdge){ result = power(2, components, MOD) -1; } else{ result = power(2, components, MOD); result = (result * 2) % MOD; } if(result <0) result += MOD; System.out.println(result); } static void bfs(int start){ Queue<Integer> q = new LinkedList<>(); q.add(start); visited[start] = true; while(!q.isEmpty()){ int u = q.poll(); for(int v: adj.get(u)){ if(!removed[v] && !visited[v]){ visited[v]=true; q.add(v); } } } } static long power(long a, long b, long mod){ long res=1; a %= mod; while(b >0){ if((b&1)==1){ res = res * a % mod; } a = a * a % mod; b >>=1; } return res; } }Explanation of the Code
- Input Parsing: Read the number of vertices
n, edgesm, and the specific verticesrandb. - Graph Construction: Build the adjacency list for the graph and check if there is a direct edge between
randb. - Connected Components Counting:
- Remove
randbfrom the graph. - Use BFS to count the number of connected components
cin the remaining graph.
- Remove
- Final Calculation:
- If there is a direct edge between
randb, the number of colorings is2^c - 1. - Otherwise, it's
2^(c+1). - The result is computed modulo (10^9 + 7).
- If there is a direct edge between
Conclusion
By analyzing the graph's structure and the connection between
randb, we can efficiently determine the number of possible distinct colorings. The key is to correctly count the connected components after removing the initial red and black vertices and then applying the appropriate formula based on whetherrandbare directly connected. - Graph Structure: You are given a connected graph with
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.