7268 | 2024. 01. 05 18:56:42 | czita | Elágazás nélküli úton levő települések (50 pont) | csharp | Elfogadva 50/50 | 116ms | 38880 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];
List<List<int>> V = new List<List<int>>();
for (int i = 0; i < N + 1; i++)
{
V.Add(new List<int>());
}
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>();
List<int> jotel = new List<int>();
HashSet<int> megold = new HashSet<int>();
bool[] volt = new bool[N + 1];
for (int i = 0; i < V.Count; i++)
{
if (V[i].Count == 1)
{
zsakfalu.Add(i);
jotel.Add(V[i][0]);
megold.Add(V[i][0]);
}
}
foreach (var item in zsakfalu)
{
int tel = item, kovtel,elozotel=0;
while (V[tel].Count <= 2)
{
if (V[tel].Count==1)
{
megold.Add(V[tel][0]);
kovtel = V[tel][0];
elozotel = tel;
tel = kovtel;
if(V[kovtel].Count == 1)
{
break;
}
}
else
{
if (V[tel][0]!=elozotel)
{
kovtel = V[tel][0];
}
else
{
kovtel = V[tel][1];
}
megold.Add(kovtel);
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 | 24620 KiB | |||
2 | Elfogadva | 0/0 | 116ms | 35888 KiB | |||
3 | Elfogadva | 2/2 | 43ms | 25256 KiB | |||
4 | Elfogadva | 2/2 | 43ms | 25188 KiB | |||
5 | Elfogadva | 2/2 | 39ms | 25396 KiB | |||
6 | Elfogadva | 2/2 | 43ms | 25472 KiB | |||
7 | Elfogadva | 2/2 | 43ms | 25400 KiB | |||
8 | Elfogadva | 2/2 | 48ms | 28084 KiB | |||
9 | Elfogadva | 2/2 | 56ms | 29964 KiB | |||
10 | Elfogadva | 2/2 | 63ms | 32420 KiB | |||
11 | Elfogadva | 2/2 | 79ms | 35484 KiB | |||
12 | Elfogadva | 2/2 | 82ms | 36012 KiB | |||
13 | Elfogadva | 3/3 | 46ms | 28452 KiB | |||
14 | Elfogadva | 3/3 | 50ms | 30296 KiB | |||
15 | Elfogadva | 3/3 | 54ms | 30876 KiB | |||
16 | Elfogadva | 3/3 | 56ms | 31508 KiB | |||
17 | Elfogadva | 3/3 | 75ms | 37124 KiB | |||
18 | Elfogadva | 3/3 | 76ms | 37328 KiB | |||
19 | Elfogadva | 3/3 | 87ms | 37724 KiB | |||
20 | Elfogadva | 3/3 | 112ms | 38580 KiB | |||
21 | Elfogadva | 3/3 | 116ms | 38820 KiB | |||
22 | Elfogadva | 3/3 | 116ms | 38880 KiB |