7774 2024. 01. 11 09:32:54 NotYou Elágazás nélküli úton levő települések (50 pont) csharp Elfogadva 50/50 109ms 36452 KiB
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StopElagazas
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] inp = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int n = inp[0] + 1;
            int m = inp[1];
            int[] l = new int[2];
            List<int>[] cities = new List<int>[n + 1];
            List<int> bag = new List<int>();
            for (int i = 0; i < n; i++)
            {
                cities[i] = new List<int>();
            }
            for (int i = 0; i < m; i++)
            {
                l = Console.ReadLine().Split().Select(int.Parse).ToArray();
                cities[l[1]].Add(l[0]);
                cities[l[0]].Add(l[1]);
            }
            for (int i = 1; i < n; i++)
            {
                if (cities[i].Count == 1)
                {
                    bag.Add(i);
                }
            }
            int last = -1;
            int dis;
            List<int> sol = new List<int>();
            for (int i = 0; i < bag.Count; i++)
            {
                dis = bag[i];
                while (true)
                {
                    if (dis == bag[i])
                    {
                        last = dis;
                        dis = cities[bag[i]].First();
                        if (!sol.Contains(dis))
                        {
                            sol.Add(dis);
                        }
                    }
                    else if (cities[dis].Count == 2)
                    {
                        if (cities[dis][0] == last)
                        {
                            last = dis;
                            dis = cities[dis][1];
                        }
                        else
                        {
                            last = dis;
                            dis = cities[dis][0];
                        }
                        if (!sol.Contains(dis))
                        {
                            sol.Add(dis);
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }
            Console.WriteLine(sol.Count);
            sol.Sort();
            for (int i = 0; i < sol.Count; i++)
            {
                Console.Write(sol[i] + " ");
            }
            Console.ReadLine();
        }
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 35ms 22212 KiB
2 Elfogadva 0/0 108ms 33332 KiB
3 Elfogadva 2/2 37ms 23532 KiB
4 Elfogadva 2/2 35ms 23696 KiB
5 Elfogadva 2/2 32ms 23720 KiB
6 Elfogadva 2/2 35ms 23960 KiB
7 Elfogadva 2/2 37ms 24244 KiB
8 Elfogadva 2/2 41ms 26016 KiB
9 Elfogadva 2/2 48ms 28028 KiB
10 Elfogadva 2/2 56ms 30704 KiB
11 Elfogadva 2/2 68ms 33776 KiB
12 Elfogadva 2/2 71ms 34348 KiB
13 Elfogadva 3/3 39ms 26924 KiB
14 Elfogadva 3/3 43ms 28372 KiB
15 Elfogadva 3/3 48ms 29080 KiB
16 Elfogadva 3/3 56ms 29356 KiB
17 Elfogadva 3/3 70ms 35320 KiB
18 Elfogadva 3/3 70ms 35284 KiB
19 Elfogadva 3/3 79ms 35460 KiB
20 Elfogadva 3/3 105ms 36152 KiB
21 Elfogadva 3/3 109ms 36364 KiB
22 Elfogadva 3/3 108ms 36452 KiB