74802024-01-09 10:14:26CsongiElágazás nélküli úton levő települések (50 pont)csharpElfogadva 50/50107ms38284 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ÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/039ms24072 KiB
2Elfogadva0/0107ms34960 KiB
3Elfogadva2/239ms24716 KiB
4Elfogadva2/237ms25584 KiB
5Elfogadva2/235ms25300 KiB
6Elfogadva2/239ms25496 KiB
7Elfogadva2/239ms25876 KiB
8Elfogadva2/243ms27628 KiB
9Elfogadva2/250ms29452 KiB
10Elfogadva2/257ms31756 KiB
11Elfogadva2/271ms35244 KiB
12Elfogadva2/276ms35588 KiB
13Elfogadva3/341ms27784 KiB
14Elfogadva3/346ms29552 KiB
15Elfogadva3/348ms30008 KiB
16Elfogadva3/352ms30724 KiB
17Elfogadva3/371ms36252 KiB
18Elfogadva3/372ms36716 KiB
19Elfogadva3/382ms37216 KiB
20Elfogadva3/3104ms37768 KiB
21Elfogadva3/3107ms38152 KiB
22Elfogadva3/3105ms38284 KiB