7480 2024. 01. 09 10:14:26 Csongi Elágazás nélküli úton levő települések (50 pont) csharp Elfogadva 50/50 107ms 38284 KiB
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace elagazas_nelkuli
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] be = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int n = be[0];
            int m = be[1];
            List<List<int>> csucsok = new List<List<int>>(n + 1);
            for (int i = 0; i <= n; i++)
            {
                csucsok.Add(new List<int>());
            }
            for (int i = 0; i < m; i++)
            {
                int[] bekeres = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                int a = bekeres[0];
                int b = bekeres[1];
                csucsok[a].Add(b);
                csucsok[b].Add(a);
            }
            List<int> zsakok = new List<int>();
            for (int i = 0; i < csucsok.Count; i++)
            {
                if (csucsok[i].Count == 1)
                    zsakok.Add(i);
            }
            SortedSet<int> megoldasok = new SortedSet<int>();
            foreach (int i in zsakok)
            {
                int zsak = i, kovi, elozo = 0;
                while (csucsok[zsak].Count <= 2)
                {
                    if (csucsok[zsak].Count == 1)
                    {
                        kovi = csucsok[zsak][0];
                        megoldasok.Add(csucsok[zsak][0]);
                        elozo = zsak;
                        zsak = kovi;
                        if (csucsok[kovi].Count == 1)
                            break;
                    }
                    else
                    {
                        if (csucsok[zsak][0] == elozo)
                        {
                            kovi = csucsok[zsak][1];
                        }
                        else
                            kovi = csucsok[zsak][0];
                        megoldasok.Add(kovi);
                        elozo = zsak;
                        zsak = kovi;
                        if (csucsok[kovi].Count == 1)
                            break;
                    }
                }
            }
            Console.WriteLine(megoldasok.Count);
            if (megoldasok.Count != 0)
            {
                foreach (int i in megoldasok)
                {
                    Console.Write(i + " ");
                }
            }
            else
                Console.WriteLine();
            Console.ReadKey();
        }
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 39ms 24072 KiB
2 Elfogadva 0/0 107ms 34960 KiB
3 Elfogadva 2/2 39ms 24716 KiB
4 Elfogadva 2/2 37ms 25584 KiB
5 Elfogadva 2/2 35ms 25300 KiB
6 Elfogadva 2/2 39ms 25496 KiB
7 Elfogadva 2/2 39ms 25876 KiB
8 Elfogadva 2/2 43ms 27628 KiB
9 Elfogadva 2/2 50ms 29452 KiB
10 Elfogadva 2/2 57ms 31756 KiB
11 Elfogadva 2/2 71ms 35244 KiB
12 Elfogadva 2/2 76ms 35588 KiB
13 Elfogadva 3/3 41ms 27784 KiB
14 Elfogadva 3/3 46ms 29552 KiB
15 Elfogadva 3/3 48ms 30008 KiB
16 Elfogadva 3/3 52ms 30724 KiB
17 Elfogadva 3/3 71ms 36252 KiB
18 Elfogadva 3/3 72ms 36716 KiB
19 Elfogadva 3/3 82ms 37216 KiB
20 Elfogadva 3/3 104ms 37768 KiB
21 Elfogadva 3/3 107ms 38152 KiB
22 Elfogadva 3/3 105ms 38284 KiB