198882025-12-28 23:25:52szabelrElágazás nélküli úton levő települések (50 pont)cpp17Hibás válasz 39/5013ms1332 KiB
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    // 1. FAST I/O: Essential for C++ speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<vector<int>> adj(n + 1);
    int u, v;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 2. MEMORY: vector<char> is faster to access than vector<bool>
    // 'visited' tracks traversal, 'is_solution' marks nodes to print later
    vector<char> visited(n + 1, 0);
    vector<char> is_solution(n + 1, 0);
    int count = 0;

    for (int i = 1; i <= n; i++)
    {
        // Only start searching from "dead ends" (degree 1)
        if (adj[i].size() == 1)
        {
            int prev = i;
            int curr = adj[i][0];

            // If we already processed this path from the other end, skip it
            if (visited[curr]) continue;

            while (true)
            {
                // Mark current node as part of the result
                visited[curr] = 1;
                is_solution[curr] = 1;
                count++;

                // If this is a junction or end of line (degree != 2), we stop
                // (We stop AFTER adding it, to match your original logic)
                if (adj[curr].size() != 2) break;

                // 3. MATH TRICK: Branchless neighbor finding
                // Since degree is 2, neighbors are {A, B}. We came from A.
                // Next = (A + B) - A  => B
                int next_node = adj[curr][0] + adj[curr][1] - prev;

                prev = curr;
                curr = next_node;

                // Safety break if we hit a visited node (cycle or merge)
                if (visited[curr]) break;
            }
        }
    }

    // 4. LINEAR OUTPUT: Iterate 1..N instead of sorting
    // This replaces the O(N log N) sort with an O(N) loop
    cout << count << "\n";
    bool first = true;
    for (int i = 1; i <= n; i++)
    {
        if (is_solution[i]) 
        {
            if (!first) cout << " ";
            cout << i;
            first = false;
        }
    }

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base39/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/013ms1332 KiB
3Hibás válasz0/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms508 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/22ms488 KiB
9Elfogadva2/23ms524 KiB
10Elfogadva2/24ms564 KiB
11Elfogadva2/27ms848 KiB
12Elfogadva2/27ms820 KiB
13Elfogadva3/32ms500 KiB
14Elfogadva3/32ms316 KiB
15Hibás válasz0/33ms564 KiB
16Hibás válasz0/34ms668 KiB
17Elfogadva3/36ms848 KiB
18Hibás válasz0/37ms936 KiB
19Elfogadva3/38ms940 KiB
20Elfogadva3/312ms1076 KiB
21Elfogadva3/313ms1212 KiB
22Elfogadva3/313ms1332 KiB