74302024-01-08 22:38:05CsongiElágazás nélküli úton levő települések (50 pont)csharpHibás válasz 4/50109ms68728 KiB
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace zsakfalu
{
    internal class Program
    {

        static int[] bfs(List<List<int>> csucslista, int v, int n)
        {
            List<int> path = new List<int>();
            bool[] check = new bool[n+1];
            Queue<int> sor = new Queue<int>(n+1);
            sor.Enqueue(v);
            check[v] = true;
            bool breakk = false;
            while (sor.Count > 0)
            {
                int most = sor.Dequeue();

                foreach (int szomszed in csucslista[most])
                {
                    if (!check[szomszed])
                    {
                        
                        if (csucslista[szomszed].Count < 3)
                        {
                            path.Add(szomszed);
                            sor.Enqueue(szomszed);
                            check[szomszed] = true;
                            
                        }
                        else
                        {
                            path.Add(szomszed);
                            sor.Enqueue(szomszed);
                            check[szomszed] = true;
                            breakk = true;
                            break;
                        }
                        
                    }
                    
                }
                if (breakk)
                    break;
            }
            return path.ToArray();
        }

        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>>();
            for (int i = 0; i <= n; i++)
            {
                csucsok.Add(new List<int>());
            }
            for(int i = 1; i <= m; i++)
            {
                int[] be1 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                csucsok[be1[0]].Add(be1[1]);
                csucsok[be1[1]].Add(be1[0]);
                
            }
            int[] fokszamok = new int[n+1];
            fokszamok[0] = 0;
            for (int i = 1; i <= n; i++)
            {
                fokszamok[i] = csucsok[i].Count;
            }
            List<int> bfss = new List<int>();
            int hanydarabzsak = fokszamok.Count(c => c == 1);
            for (int i = 1; i < fokszamok.Length; i++)
            {
                if (fokszamok[i] == 1) //amelyik zsakfalu
                {
                    int[] a = bfs(csucsok, i, n);
                    for (int j = 0; j < a.Length; j++)
                    {
                        bfss.Add(a[j]);
                    }
                }
            }
            Console.WriteLine(bfss.Count);
            foreach (int i in bfss)
            {
                Console.Write(i + " ");
            }


            Console.ReadKey();
        }
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base4/50
1Elfogadva0/037ms22540 KiB
2Hibás válasz0/0105ms36480 KiB
3Hibás válasz0/235ms23328 KiB
4Hibás válasz0/235ms23728 KiB
5Elfogadva2/235ms23612 KiB
6Hibás válasz0/235ms24384 KiB
7Hibás válasz0/235ms24508 KiB
8Hibás válasz0/241ms26488 KiB
9Hibás válasz0/250ms28296 KiB
10Hibás válasz0/254ms31396 KiB
11Elfogadva2/271ms33968 KiB
12Hibás válasz0/272ms34700 KiB
13Hibás válasz0/339ms27044 KiB
14Hibás válasz0/345ms30556 KiB
15Hibás válasz0/350ms40772 KiB
16Hibás válasz0/375ms68176 KiB
17Hibás válasz0/379ms54960 KiB
18Hibás válasz0/382ms68728 KiB
19Hibás válasz0/392ms65356 KiB
20Hibás válasz0/3105ms38268 KiB
21Hibás válasz0/3109ms39296 KiB
22Hibás válasz0/3109ms40328 KiB