Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

یک گراف ساده‌ی همبند n n راسی به شما داده است. در ابتدا رنگ تمامی راس‌ها به جز دو راس r…

  1. 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

  2. Assistant

    برای حل این مسئله، باید تعداد رنگ‌آمیزی‌های متفاوت نهایی گراف را که بر اساس فرآیند پراکندگی مهره‌های قرمز و سیاه ایجاد می‌شود، محاسبه کنیم. فرآیند به این صورت است که در هر گام تصادفی یکی از دو رنگ قرمز یا سیاه انتخاب شده و مهره‌های آن رنگ در تمامی رئوس همسایه گسترش می‌یابند. هر راس به محض دریافت اولین مهره از یک رنگ، رنگ آن تعیین می‌شود و دیگر تغییر نخواهد کرد.

    گام‌های حل مسئله:

    1. محاسبه فاصله‌ها:

      • فاصله هر راس از راس r (فاصله قرمز) و راس b (فاصله سیاه) را با استفاده از الگوریتم BFS محاسبه می‌کنیم.
    2. تعیین انتخاب‌های آزاد:

      • برای هر راس، اگر فاصله آن از r برابر با فاصله آن از b باشد، این راس می‌تواند به دو صورت قرمز یا سیاه رنگ شود. تعداد این رئوس را به عنوان k تعیین می‌کنیم.
      • اگر فاصله از r کمتر از فاصله از b باشد، این راس باید قرمز باشد و اگر فاصله از b کمتر بود، باید سیاه باشد.
    3. محاسبه تعداد رنگ‌آمیزی‌های مختلف:

      • تعداد رنگ‌آمیزی‌های متفاوت برابر است با (2^k) که در آن k تعداد رئوس با فاصله‌های مساوی از r و b است.
      • در نهایت، مقدار نهایی را بر (10^9 + 7) باقی‌مانده می‌کنیم تا خروجی نهایی به دست آید.

    با این تحلیل، کد زیر پیاده‌سازی شده است:

    import sys
    import sys
    import sys
    from collections import deque
    
    MOD = 10**9 +7
    
    def main():
        import sys
        sys.setrecursionlimit(1 << 25)
        n, m, r, b = map(int, sys.stdin.readline().split())
        adj = [[] for _ in range(n+1)]
        for _ in range(m):
            u,v = map(int, sys.stdin.readline().split())
            adj[u].append(v)
            adj[v].append(u)
        
        def bfs(start):
            dist = [ -1 ] * (n+1)
            q = deque()
            q.append(start)
            dist[start]=0
            while q:
                u = q.popleft()
                for v in adj[u]:
                    if dist[v]==-1:
                        dist[v]=dist[u]+1
                        q.append(v)
            return dist
        
        dr = bfs(r)
        db = bfs(b)
        
        k=0
        for v in range(1,n+1):
            if v == r or v == b:
                continue
            if dr[v]==db[v] and dr[v]!= -1:
                k+=1
        ans = pow(2,k, MOD)
        print(ans)
        
    if __name__ == "__main__":
        main()
    

    توضیح نهایی: این کد ابتدا فاصله هر راس از رئوس r و b را محاسبه می‌کند. سپس تعداد رئوس با فاصله‌های مساوی از r و b را شمارش کرده و نهایتاً تعداد رنگ‌آمیزی‌های ممکن را به صورت (2^k) محاسبه می‌کند. نتیجه نهایی بر (10^9 + 7) باقی‌مانده و چاپ می‌شود.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.