5776 | 2023. 09. 27 07:39:29 | zsebi | Elágazás nélküli úton levő települések (50 pont) | cpp11 | Hibás válasz 31/50 | 29ms | 6928 KiB |
// elagazas nelkul.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
struct adat
{
bool lat = false;
vector<ll>sz;
};
ll n, m;
int main()
{
cin >> n >> m;
vector<adat>x(n+1);
vector<ll>ans;
for (int i = 1; i <= m; ++i)
{
ll a, b;
cin >> a >> b;
x[a].sz.push_back(b);
x[b].sz.push_back(a);
}
vector<ll>falu;
for (int i = 1; i <= n; ++i)
{
if (x[i].sz.size() == 1)falu.push_back(i);
}
for (auto b:falu)
{
deque<ll>v;
v.push_back(b);
vector<ll>volt;
while (!v.empty())
{
ll akt = v.front();
volt.push_back(akt);
v.pop_front();
x[akt].lat = true;
for (auto& e : x[akt].sz)
{
auto res = find(volt.begin(), volt.end(), e);
if (res == end(volt))
{
if (!x[e].lat)
{
ans.push_back(e);
x[e].lat = true;
}
if (x[e].sz.size() <= 2)
{
v.push_back(e);
}
}
}
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << "\n";
for (auto& e : ans)cout << e<<" ";
return 0;
}
/*8 9
1 2
1 6
2 7
1 5
3 4
4 5
5 6
6 7
8 7*/
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 31/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1684 KiB | |||
2 | Elfogadva | 0/0 | 29ms | 4840 KiB | |||
3 | Hibás válasz | 0/2 | 3ms | 2220 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2348 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2560 KiB | |||
6 | Hibás válasz | 0/2 | 3ms | 2732 KiB | |||
7 | Elfogadva | 2/2 | 2ms | 2780 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3284 KiB | |||
9 | Elfogadva | 2/2 | 6ms | 3500 KiB | |||
10 | Elfogadva | 2/2 | 8ms | 3908 KiB | |||
11 | Elfogadva | 2/2 | 16ms | 4812 KiB | |||
12 | Elfogadva | 2/2 | 16ms | 4752 KiB | |||
13 | Elfogadva | 3/3 | 4ms | 3520 KiB | |||
14 | Hibás válasz | 0/3 | 4ms | 3752 KiB | |||
15 | Hibás válasz | 0/3 | 6ms | 3952 KiB | |||
16 | Hibás válasz | 0/3 | 6ms | 4128 KiB | |||
17 | Hibás válasz | 0/3 | 14ms | 4904 KiB | |||
18 | Hibás válasz | 0/3 | 14ms | 4992 KiB | |||
19 | Elfogadva | 3/3 | 17ms | 5384 KiB | |||
20 | Elfogadva | 3/3 | 28ms | 6324 KiB | |||
21 | Elfogadva | 3/3 | 29ms | 6928 KiB | |||
22 | Elfogadva | 3/3 | 29ms | 6852 KiB |