78282024-01-11 12:24:26gyjazminElágazás nélküli úton levő települések (50 pont)cpp17Elfogadva 50/5085ms11856 KiB
#include <vector>
#include <iostream>
#include <set>
using namespace std;
vector<set<int>> graf;
set<int> valasz;
int n, m;
void bejaras(int a) {
    vector<int> vizsg;
    vizsg.push_back(a);
    bool tobb = false;
    vector<bool> volt(n + 1);
    volt[a] = true;
    while (!tobb) {
        for (int i = 1;i < n + 1;i++) {
            if (/*graf[vizsg[0]][i]*/ graf[vizsg[0]].count(i)== 1 && !volt[i]) {
                vizsg.push_back(i);
                volt[i] = true;
            }
        }
        vizsg.erase(vizsg.begin());
        if (vizsg.size() == 1) {
            valasz.insert(vizsg[0]);
        }
        else tobb = true;

    }


}
int main()
{
    cin >> n >> m;
    vector<int> utak(n + 1);
    graf.resize(n + 1);
    /*for (int i = 1;i < n + 1;i++) {
        graf[i].resize(n + 1);
    }*/
    for (int i = 1;i < m + 1;i++) {
        int egyik, masik;
        cin >> egyik >> masik;
        //graf[egyik][masik] = 1;
        //graf[masik][egyik] = 1;
        graf[egyik].insert(masik);
        graf[masik].insert(egyik);
        utak[egyik]++;
        utak[masik]++;
    }
    for (int i = 1;i < n + 1;i++) {
        if (utak[i] == 1) {
            bejaras(i);
        }
    }
    cout << valasz.size() << endl;
    if (valasz.size() != 0) {
        for (int x : valasz) {
            cout << x << " ";
        }
        cout << endl;
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1808 KiB
2Elfogadva0/041ms10376 KiB
3Elfogadva2/23ms2224 KiB
4Elfogadva2/23ms2392 KiB
5Elfogadva2/23ms2476 KiB
6Elfogadva2/23ms2724 KiB
7Elfogadva2/23ms2808 KiB
8Elfogadva2/24ms3344 KiB
9Elfogadva2/28ms4060 KiB
10Elfogadva2/212ms5008 KiB
11Elfogadva2/219ms6720 KiB
12Elfogadva2/219ms6788 KiB
13Elfogadva3/34ms3232 KiB
14Elfogadva3/38ms3988 KiB
15Elfogadva3/318ms4232 KiB
16Elfogadva3/385ms4464 KiB
17Elfogadva3/341ms6756 KiB
18Elfogadva3/357ms7224 KiB
19Elfogadva3/350ms8504 KiB
20Elfogadva3/337ms11644 KiB
21Elfogadva3/339ms11788 KiB
22Elfogadva3/341ms11856 KiB