77032024-01-10 13:54:37AblablablaElágazás nélküli úton levő települések (50 pont)cpp17Accepted 50/5029ms6368 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";
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1996 KiB
2Accepted0/029ms3916 KiB
3Accepted2/23ms2128 KiB
4Accepted2/23ms2264 KiB
5Accepted2/23ms2496 KiB
6Accepted2/22ms2476 KiB
7Accepted2/23ms2508 KiB
8Accepted2/24ms2552 KiB
9Accepted2/26ms2768 KiB
10Accepted2/28ms3116 KiB
11Accepted2/216ms3768 KiB
12Accepted2/216ms4024 KiB
13Accepted3/34ms3396 KiB
14Accepted3/34ms3760 KiB
15Accepted3/36ms4156 KiB
16Accepted3/37ms4212 KiB
17Accepted3/314ms4496 KiB
18Accepted3/314ms4644 KiB
19Accepted3/317ms5292 KiB
20Accepted3/328ms5636 KiB
21Accepted3/329ms6092 KiB
22Accepted3/329ms6368 KiB