8242 2024. 01. 13 19:53:17 czita Kerékpártúra (50 pont) csharp Elfogadva 50/50 393ms 47972 KiB
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace kerekpar
{
    class pont
    {
        public char szin;
        public List<int> hova;
        public List<int> honnan;
        public pont()
        {
            hova = new List<int>();
            honnan = new List<int>();
            szin = 'W'; //B Black, W white G Gray
        }
    }
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] t = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = t[0]; int M = t[1]; int K = t[2];
            pont[] G = new pont[N + 1];
            for (int i = 0; i < N + 1; i++) G[i] = new pont();
            for (int i = 0; i < M; i++)
            {
                t = Console.ReadLine().Split().Select(int.Parse).ToArray();
                G[t[0]].hova.Add(t[1]);
                G[t[1]].honnan.Add(t[0]);
            }
            List<int> Q = new List<int>(); 
            G[K].szin = 'B';
            Q.Add(K);
            int p;
            //ki érhető el az adott pontból
            while (Q.Count > 0) 
            {
                p = Q[0];
                Q.RemoveAt(0);
                foreach (int i in G[p].hova) 
                {
                  if (G[i].szin=='W') 
                    {
                        G[i].szin = 'G';
                        Q.Add(i);
                    }
                }
            }
            //a kezdőpontből elérhető pontok közül ki éri el valamely kezdőpontot elérő pontot
            Q.Add(K);
            List<int> E = new List<int>();
            E.Add(K);
            while (Q.Count > 0)
            {
                p = Q[0];
                Q.RemoveAt(0);
                foreach (int i in G[p].honnan)
                {
                    if (G[i].szin == 'G')
                    {
                        G[i].szin = 'B';
                        Q.Add(i);
                        E.Add(i);
                    }
                }
            }
            
            HashSet<int> S = new HashSet<int>(E);    
            S.Remove(K);    
            //a azokból a pontokból, amelyekból elérhető a kezdőpont közvetlenül nyíló pontokat betesszük
            foreach (int i in E)
            {
                foreach (var v in G[i].hova)
                {
                    if (G[v].szin=='G')
                    {
                        S.Add(v);
                    }
                }
            }
            Console.WriteLine(S.Count);
            Console.WriteLine(string.Join(" ",S));
            Console.ReadKey();
        }
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 37ms 23824 KiB
2 Elfogadva 0/0 96ms 36860 KiB
3 Elfogadva 2/2 37ms 24552 KiB
4 Elfogadva 2/2 39ms 24876 KiB
5 Elfogadva 2/2 37ms 25208 KiB
6 Elfogadva 2/2 41ms 26300 KiB
7 Elfogadva 2/2 39ms 26344 KiB
8 Elfogadva 2/2 43ms 27984 KiB
9 Elfogadva 2/2 45ms 27720 KiB
10 Elfogadva 2/2 50ms 28784 KiB
11 Elfogadva 2/2 50ms 30244 KiB
12 Elfogadva 2/2 75ms 34660 KiB
13 Elfogadva 2/2 71ms 35324 KiB
14 Elfogadva 2/2 109ms 36160 KiB
15 Elfogadva 3/3 138ms 40780 KiB
16 Elfogadva 4/4 145ms 40928 KiB
17 Elfogadva 4/4 181ms 43552 KiB
18 Elfogadva 3/3 166ms 42796 KiB
19 Elfogadva 3/3 159ms 42868 KiB
20 Elfogadva 3/3 354ms 46380 KiB
21 Elfogadva 3/3 393ms 47572 KiB
22 Elfogadva 3/3 391ms 47972 KiB