255102026-02-20 12:59:45vobaSportos nyaraláscsharpFutási hiba 0/4014ms3016 KiB
using System;
using System.Collections.Generic;

class Program
{
    static int[] bikeComp, waterComp;
    
    static void Main()
    {
        var line = Console.ReadLine().Split();
        int N = int.Parse(line[0]);
        int M = int.Parse(line[1]);
        int K = int.Parse(line[2]);

        var bikeAdj = new List<int>[N + 1];
        var waterAdj = new List<int>[N + 1];
        for (int i = 1; i <= N; i++)
        {
            bikeAdj[i] = new List<int>();
            waterAdj[i] = new List<int>();
        }

        for (int i = 0; i < M; i++)
        {
            var parts = Console.ReadLine().Split();
            int a = int.Parse(parts[0]), b = int.Parse(parts[1]);
            bikeAdj[a].Add(b);
            bikeAdj[b].Add(a);
        }
        for (int i = 0; i < K; i++)
        {
            var parts = Console.ReadLine().Split();
            int a = int.Parse(parts[0]), b = int.Parse(parts[1]);
            waterAdj[a].Add(b);
            waterAdj[b].Add(a);
        }

        bikeComp = new int[N + 1];
        waterComp = new int[N + 1];
        var bikeSize = new Dictionary<int, int>();
        var waterSize = new Dictionary<int, int>();

        // BFS to find components
        BFS(N, bikeAdj, bikeComp, bikeSize);
        BFS(N, waterAdj, waterComp, waterSize);

        // For each node, count: |bikeComp| + |waterComp| - |intersection| - 1
        // Intersection: nodes with same bikeComp AND same waterComp
        // We need to count pairs (bikeComp[i], waterComp[i]) occurrences
        var pairCount = new Dictionary<long, int>();
        for (int i = 1; i <= N; i++)
        {
            long key = (long)bikeComp[i] * 100001 + waterComp[i];
            if (!pairCount.ContainsKey(key)) pairCount[key] = 0;
            pairCount[key]++;
        }

        var result = new System.Text.StringBuilder();
        for (int i = 1; i <= N; i++)
        {
            long key = (long)bikeComp[i] * 100001 + waterComp[i];
            int bc = bikeSize[bikeComp[i]];
            int wc = waterSize[waterComp[i]];
            int inter = pairCount[key];
            int ans = bc + wc - inter - 1;
            if (i > 1) result.Append(' ');
            result.Append(ans);
        }
        Console.WriteLine(result);
    }

    static void BFS(int N, List<int>[] adj, int[] comp, Dictionary<int, int> size)
    {
        int compId = 0;
        var queue = new Queue<int>();
        for (int i = 1; i <= N; i++)
        {
            if (comp[i] == 0)
            {
                compId++;
                comp[i] = compId;
                queue.Enqueue(i);
                int cnt = 0;
                while (queue.Count > 0)
                {
                    int cur = queue.Dequeue();
                    cnt++;
                    foreach (var nb in adj[cur])
                    {
                        if (comp[nb] == 0)
                        {
                            comp[nb] = compId;
                            queue.Enqueue(nb);
                        }
                    }
                }
                size[compId] = cnt;
            }
        }
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/40
1Futási hiba0/014ms2752 KiB
2Futási hiba0/014ms2580 KiB
3Futási hiba0/114ms2832 KiB
4Futási hiba0/114ms2772 KiB
5Futási hiba0/114ms2776 KiB
6Futási hiba0/114ms2596 KiB
7Futási hiba0/114ms2828 KiB
8Futási hiba0/114ms2880 KiB
9Futási hiba0/114ms2808 KiB
10Futási hiba0/114ms2948 KiB
11Futási hiba0/214ms2848 KiB
12Futási hiba0/214ms2752 KiB
13Futási hiba0/214ms2784 KiB
14Futási hiba0/214ms2696 KiB
15Futási hiba0/214ms2788 KiB
16Futási hiba0/214ms2792 KiB
17Futási hiba0/314ms2864 KiB
18Futási hiba0/314ms2760 KiB
19Futási hiba0/214ms3016 KiB
20Futási hiba0/214ms2832 KiB
21Futási hiba0/214ms2840 KiB
22Futási hiba0/214ms2856 KiB
23Futási hiba0/314ms2952 KiB
24Futási hiba0/314ms2776 KiB