7271 | 2024. 01. 05 19:31:11 | czita | Elágazás nélküli úton levő települések (50 pont) | csharp | Elfogadva 50/50 | 116ms | 39388 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
SortedSet<int> megold = new SortedSet<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(" ", megold));
Console.ReadKey();
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 39ms | 24316 KiB | |||
2 | Elfogadva | 0/0 | 115ms | 35700 KiB | |||
3 | Elfogadva | 2/2 | 39ms | 25328 KiB | |||
4 | Elfogadva | 2/2 | 39ms | 25416 KiB | |||
5 | Elfogadva | 2/2 | 37ms | 25868 KiB | |||
6 | Elfogadva | 2/2 | 41ms | 26200 KiB | |||
7 | Elfogadva | 2/2 | 39ms | 26332 KiB | |||
8 | Elfogadva | 2/2 | 46ms | 27928 KiB | |||
9 | Elfogadva | 2/2 | 52ms | 30032 KiB | |||
10 | Elfogadva | 2/2 | 63ms | 32608 KiB | |||
11 | Elfogadva | 2/2 | 79ms | 35664 KiB | |||
12 | Elfogadva | 2/2 | 76ms | 36624 KiB | |||
13 | Elfogadva | 3/3 | 43ms | 28660 KiB | |||
14 | Elfogadva | 3/3 | 48ms | 30040 KiB | |||
15 | Elfogadva | 3/3 | 50ms | 30516 KiB | |||
16 | Elfogadva | 3/3 | 54ms | 31316 KiB | |||
17 | Elfogadva | 3/3 | 71ms | 37160 KiB | |||
18 | Elfogadva | 3/3 | 78ms | 37424 KiB | |||
19 | Elfogadva | 3/3 | 82ms | 37872 KiB | |||
20 | Elfogadva | 3/3 | 115ms | 38908 KiB | |||
21 | Elfogadva | 3/3 | 116ms | 39388 KiB | |||
22 | Elfogadva | 3/3 | 116ms | 39184 KiB |