178632025-09-19 20:38:44KristófElágazás nélküli úton levő települések (50 pont)cpp17Hibás válasz 4/5028ms1332 KiB
#include <iostream>
#include <vector>
#include <set>
using namespace std;

void solver(vector<bool> &visit, int s, const vector<vector<int>> &graph, set<int> &ans) {
    visit[s] = true;
    ans.insert(s);

    if (graph[s].size() == 2) {  // lánc belső csúcs
        for (int x : graph[s]) {
            if (!visit[x])
                solver(visit, x, graph, ans);
        }
    }
    // deg != 2 → elágazás vagy zsákfalu, csak beszúrjuk az ans-be, nem megyünk tovább
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> ends;
    for (int i = 1; i <= n; i++)
        if (graph[i].size() == 1)
            ends.push_back(i);

    vector<bool> visit(n + 1, false);
    set<int> ans;

    for (int i : ends) {
        if (!visit[i]) {
            visit[i] = true;
            ans.insert(i);  // kezdő zsákfalu is a kimenet része
            int neighbor = graph[i][0];
            if (!visit[neighbor])
                solver(visit, neighbor, graph, ans);
        }
    }

    cout << ans.size() << endl;
    for (int x : ans) cout << x << " ";
    cout << endl;

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base4/50
1Hibás válasz0/01ms316 KiB
2Hibás válasz0/027ms1332 KiB
3Elfogadva2/21ms316 KiB
4Hibás válasz0/21ms316 KiB
5Elfogadva2/21ms352 KiB
6Hibás válasz0/21ms316 KiB
7Hibás válasz0/21ms316 KiB
8Hibás válasz0/23ms316 KiB
9Hibás válasz0/24ms564 KiB
10Hibás válasz0/27ms632 KiB
11Hibás válasz0/214ms748 KiB
12Hibás válasz0/214ms824 KiB
13Hibás válasz0/32ms444 KiB
14Hibás válasz0/33ms536 KiB
15Hibás válasz0/34ms564 KiB
16Hibás válasz0/36ms684 KiB
17Hibás válasz0/312ms844 KiB
18Hibás válasz0/313ms752 KiB
19Hibás válasz0/316ms1032 KiB
20Hibás válasz0/326ms1212 KiB
21Hibás válasz0/328ms1272 KiB
22Hibás válasz0/328ms1332 KiB