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 |