7271 2024. 01. 05 19:31:11 czita Elágazás nélküli úton levő települések (50 pont) csharp Elfogadva 50/50 116ms 39388 KiB
using System;
using System.Collections.Generic;
using System.Linq;


namespace lenelktel
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] st = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = st[0];
            int M = st[1];
            //els sor beolvasása
            List<List<int>> V = new List<List<int>>();
            //csúcslita létrehozása
            for (int i = 0; i < N + 1; i++) V.Add(new List<int>());
            //cscslita feltöltése üres listákkal, +1 elem az indexelés miatt
            //Az élek beolvaásáa
            for (int i = 0; i < M; i++)
            {
                st = Console.ReadLine().Split().Select(int.Parse).ToArray();
                V[st[0]].Add(st[1]);
                V[st[1]].Add(st[0]);
            }
            HashSet<int> zsakfalu = new HashSet<int>();
            //ide gyűjtjük ki a zsáffalu településeket
            SortedSet<int> megold = new SortedSet<int>();
            //Ide gyűjtjük a zsákfalukból elérhető településeket
            //zsákfalvak kiválsztása
            for (int i = 0; i < V.Count; i++)
                if (V[i].Count == 1)
                {
                    zsakfalu.Add(i);
                  //  megold.Add(V[i][0]);
                }
            //zsákfalvakból eléhető települések biztosan a megoldás részei
            foreach (var item in zsakfalu)
            {
                int tel = item, kovtel, elozotel = 0;
                while (V[tel].Count <= 2)//ha zsákfalu, vagy csak két út vezet el.
                {
                    if (V[tel].Count == 1)//ha az aktuális tel. zsákfalu
                    {
                        megold.Add(V[tel][0]);
                        //beteszsük a megoldások közé
                        kovtel = V[tel][0];
                        //a következő település az aktuális egyetlen kijárata lesz
                        elozotel = tel;
                        //Az előző lesz az aktuális
                        tel = kovtel;
                        //az aktuális lesz az következő
                        if (V[kovtel].Count == 1) break;
                        //ha akövetkező település zsákfalu
                    }
                    else//ha nem zsákfalu
                    {
                        if (V[tel][0] != elozotel)
                            kovtel = V[tel][0];//ha az adott kijárat nem az előző település
                        else
                            kovtel = V[tel][1];//Ha az  adott kijárat az előző település
                        megold.Add(kovtel);//beteszsük megoldások közé
                        elozotel = tel;
                        tel = kovtel;
                        if (V[kovtel].Count == 1) break;
                    }
                }
            }
            Console.WriteLine(megold.Count);
            Console.WriteLine(string.Join(" ", megold));
            Console.ReadKey();
        }
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 39ms 24316 KiB
2 Elfogadva 0/0 115ms 35700 KiB
3 Elfogadva 2/2 39ms 25328 KiB
4 Elfogadva 2/2 39ms 25416 KiB
5 Elfogadva 2/2 37ms 25868 KiB
6 Elfogadva 2/2 41ms 26200 KiB
7 Elfogadva 2/2 39ms 26332 KiB
8 Elfogadva 2/2 46ms 27928 KiB
9 Elfogadva 2/2 52ms 30032 KiB
10 Elfogadva 2/2 63ms 32608 KiB
11 Elfogadva 2/2 79ms 35664 KiB
12 Elfogadva 2/2 76ms 36624 KiB
13 Elfogadva 3/3 43ms 28660 KiB
14 Elfogadva 3/3 48ms 30040 KiB
15 Elfogadva 3/3 50ms 30516 KiB
16 Elfogadva 3/3 54ms 31316 KiB
17 Elfogadva 3/3 71ms 37160 KiB
18 Elfogadva 3/3 78ms 37424 KiB
19 Elfogadva 3/3 82ms 37872 KiB
20 Elfogadva 3/3 115ms 38908 KiB
21 Elfogadva 3/3 116ms 39388 KiB
22 Elfogadva 3/3 116ms 39184 KiB