82422024-01-13 19:53:17czitaKerékpártúra (50 pont)csharpElfogadva 50/50393ms47972 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ÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/037ms23824 KiB
2Elfogadva0/096ms36860 KiB
3Elfogadva2/237ms24552 KiB
4Elfogadva2/239ms24876 KiB
5Elfogadva2/237ms25208 KiB
6Elfogadva2/241ms26300 KiB
7Elfogadva2/239ms26344 KiB
8Elfogadva2/243ms27984 KiB
9Elfogadva2/245ms27720 KiB
10Elfogadva2/250ms28784 KiB
11Elfogadva2/250ms30244 KiB
12Elfogadva2/275ms34660 KiB
13Elfogadva2/271ms35324 KiB
14Elfogadva2/2109ms36160 KiB
15Elfogadva3/3138ms40780 KiB
16Elfogadva4/4145ms40928 KiB
17Elfogadva4/4181ms43552 KiB
18Elfogadva3/3166ms42796 KiB
19Elfogadva3/3159ms42868 KiB
20Elfogadva3/3354ms46380 KiB
21Elfogadva3/3393ms47572 KiB
22Elfogadva3/3391ms47972 KiB