7703 2024. 01. 10 13:54:37 Ablablabla Elágazás nélküli úton levő települések (50 pont) cpp17 Elfogadva 50/50 29ms 6368 KiB
#include <bits/stdc++.h>

using namespace std;

vector<bool> bejart;
vector<vector<int>> csucsok;
vector<int> megoldas;

void dfs(int akt, int elozo){
    if(!bejart[akt]){
        megoldas.push_back(akt);
    }

    bejart[akt] = 1;

    if(csucsok[akt].size() > 2){
        return;
    }

    for(int x : csucsok[akt]){
        if(x == elozo) continue;

        dfs(x, akt);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    csucsok.assign(n, vector<int>());
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;

        csucsok[a].push_back(b);
        csucsok[b].push_back(a);
    }

    bejart.assign(n, 0);

    for(int i = 0; i < n; i++){
        if(csucsok[i].size() > 1 || csucsok[i].size() == 0) continue;

        dfs(csucsok[i][0], i);
    }

    sort(megoldas.begin(), megoldas.end());

    cout << megoldas.size() << "\n";
    for(int x : megoldas){
        cout << x + 1 << " ";
    }
    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1996 KiB
2 Elfogadva 0/0 29ms 3916 KiB
3 Elfogadva 2/2 3ms 2128 KiB
4 Elfogadva 2/2 3ms 2264 KiB
5 Elfogadva 2/2 3ms 2496 KiB
6 Elfogadva 2/2 2ms 2476 KiB
7 Elfogadva 2/2 3ms 2508 KiB
8 Elfogadva 2/2 4ms 2552 KiB
9 Elfogadva 2/2 6ms 2768 KiB
10 Elfogadva 2/2 8ms 3116 KiB
11 Elfogadva 2/2 16ms 3768 KiB
12 Elfogadva 2/2 16ms 4024 KiB
13 Elfogadva 3/3 4ms 3396 KiB
14 Elfogadva 3/3 4ms 3760 KiB
15 Elfogadva 3/3 6ms 4156 KiB
16 Elfogadva 3/3 7ms 4212 KiB
17 Elfogadva 3/3 14ms 4496 KiB
18 Elfogadva 3/3 14ms 4644 KiB
19 Elfogadva 3/3 17ms 5292 KiB
20 Elfogadva 3/3 28ms 5636 KiB
21 Elfogadva 3/3 29ms 6092 KiB
22 Elfogadva 3/3 29ms 6368 KiB