75312024-01-09 13:31:49TortelliniJrElágazás nélküli úton levő települések (50 pont)csharpElfogadva 50/50111ms37464 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ÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/035ms22532 KiB
2Elfogadva0/0108ms33228 KiB
3Elfogadva2/235ms23380 KiB
4Elfogadva2/234ms23604 KiB
5Elfogadva2/232ms24032 KiB
6Elfogadva2/234ms24140 KiB
7Elfogadva2/235ms24716 KiB
8Elfogadva2/241ms26568 KiB
9Elfogadva2/246ms28428 KiB
10Elfogadva2/256ms31084 KiB
11Elfogadva2/271ms34304 KiB
12Elfogadva2/272ms34484 KiB
13Elfogadva3/341ms27220 KiB
14Elfogadva3/345ms28556 KiB
15Elfogadva3/348ms29356 KiB
16Elfogadva3/356ms29236 KiB
17Elfogadva3/368ms35524 KiB
18Elfogadva3/371ms35668 KiB
19Elfogadva3/379ms36196 KiB
20Elfogadva3/3111ms37300 KiB
21Elfogadva3/3108ms37372 KiB
22Elfogadva3/3104ms37464 KiB