7270 | 2024. 01. 05 19:30:03 | czita | Elágazás nélküli úton levő települések (50 pont) | csharp | Elfogadva 50/50 | 116ms | 39776 KiB |
using System;
using System.Collections.Generic;
using System.Linq;
namespace lenelktel
{
class Program
{
static void Main(string[] args)
{
int[] st = Console.ReadLine().Split().Select(int.Parse).ToArray();
int N = st[0];
int M = st[1];
//els sor beolvasása
List<List<int>> V = new List<List<int>>();
//csúcslita létrehozása
for (int i = 0; i < N + 1; i++) V.Add(new List<int>());
//cscslita feltöltése üres listákkal, +1 elem az indexelés miatt
//Az élek beolvaásáa
for (int i = 0; i < M; i++)
{
st = Console.ReadLine().Split().Select(int.Parse).ToArray();
V[st[0]].Add(st[1]);
V[st[1]].Add(st[0]);
}
HashSet<int> zsakfalu = new HashSet<int>();
//ide gyűjtjük ki a zsáffalu településeket
HashSet<int> megold = new HashSet<int>();
//Ide gyűjtjük a zsákfalukból elérhető településeket
//zsákfalvak kiválsztása
for (int i = 0; i < V.Count; i++)
if (V[i].Count == 1)
{
zsakfalu.Add(i);
// megold.Add(V[i][0]);
}
//zsákfalvakból eléhető települések biztosan a megoldás részei
foreach (var item in zsakfalu)
{
int tel = item, kovtel, elozotel = 0;
while (V[tel].Count <= 2)//ha zsákfalu, vagy csak két út vezet el.
{
if (V[tel].Count == 1)//ha az aktuális tel. zsákfalu
{
megold.Add(V[tel][0]);
//beteszsük a megoldások közé
kovtel = V[tel][0];
//a következő település az aktuális egyetlen kijárata lesz
elozotel = tel;
//Az előző lesz az aktuális
tel = kovtel;
//az aktuális lesz az következő
if (V[kovtel].Count == 1) break;
//ha akövetkező település zsákfalu
}
else//ha nem zsákfalu
{
if (V[tel][0] != elozotel)
kovtel = V[tel][0];//ha az adott kijárat nem az előző település
else
kovtel = V[tel][1];//Ha az adott kijárat az előző település
megold.Add(kovtel);//beteszsük megoldások közé
elozotel = tel;
tel = kovtel;
if (V[kovtel].Count == 1) break;
}
}
}
Console.WriteLine(megold.Count);
Console.WriteLine(string.Join(" ", new SortedSet<int>(megold)));
Console.ReadKey();
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 43ms | 24272 KiB | |||
2 | Elfogadva | 0/0 | 114ms | 36096 KiB | |||
3 | Elfogadva | 2/2 | 41ms | 25204 KiB | |||
4 | Elfogadva | 2/2 | 41ms | 25316 KiB | |||
5 | Elfogadva | 2/2 | 39ms | 25512 KiB | |||
6 | Elfogadva | 2/2 | 41ms | 25916 KiB | |||
7 | Elfogadva | 2/2 | 43ms | 26112 KiB | |||
8 | Elfogadva | 2/2 | 48ms | 28332 KiB | |||
9 | Elfogadva | 2/2 | 57ms | 30196 KiB | |||
10 | Elfogadva | 2/2 | 63ms | 32556 KiB | |||
11 | Elfogadva | 2/2 | 79ms | 35708 KiB | |||
12 | Elfogadva | 2/2 | 79ms | 36280 KiB | |||
13 | Elfogadva | 3/3 | 46ms | 28908 KiB | |||
14 | Elfogadva | 3/3 | 50ms | 30156 KiB | |||
15 | Elfogadva | 3/3 | 54ms | 31160 KiB | |||
16 | Elfogadva | 3/3 | 54ms | 32128 KiB | |||
17 | Elfogadva | 3/3 | 75ms | 37296 KiB | |||
18 | Elfogadva | 3/3 | 78ms | 37656 KiB | |||
19 | Elfogadva | 3/3 | 86ms | 38080 KiB | |||
20 | Elfogadva | 3/3 | 115ms | 39436 KiB | |||
21 | Elfogadva | 3/3 | 116ms | 39712 KiB | |||
22 | Elfogadva | 3/3 | 116ms | 39776 KiB |