6145 2023. 11. 03 20:58:42 MrChipser Elágazás nélküli úton levő települések (50 pont) cpp11 Hibás válasz 31/50 29ms 6280 KiB
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;
    vector<int> adj[n];
    for(int i = 0; i < m; i++)
    {
        int x,y;
        cin >> x >> y;
        adj[x-1].push_back(y-1);
        adj[y-1].push_back(x-1);
    }
    queue<int> q;
    int zsakfalu[n] ={0};
    int votmazs[n] = {0};
    vector<int>zsakok;
    for(int i = 0; i < n; i ++)
    {
        if(adj[i].size()==1)
        {
            zsakfalu[i]=1;
            zsakok.push_back(i);
        }
    }
    int hany = 0;
    for(int i = 0; i < zsakok.size(); i++)
    {
    q.push(zsakok[i]);
    int votma[n] = {0};
    votma[zsakok[i]]=1;
    while(!q.empty())
    {
        int akt = q.front();
        q.pop();
        for(auto x : adj[akt])
        {
            //cout << akt << " "<< x << " " << adj[akt].size() <<" "<< zsakfalu[x] << endl;
            if(zsakfalu[akt]==1  && (adj[akt].size()==2 or adj[akt].size()==1))
            {
                zsakfalu[x]=1;
                if(votmazs[x]==0 && votma[x]==0)
                {
                    hany++;
                    votmazs[x]=1;
                }
                //cout << x << endl;
                if(votma[x]==0)
                {
                    votma[x]=1;
                    q.push(x);
                }
            }
        }
    }
    }
    cout << hany << endl;
    if(hany == 0)
        return 0;
    for(int i = 0; i < n; i++)
    {
        if(zsakfalu[i]==1 && adj[i].size()!=1)
            cout << i+1 << " ";
    }
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 31/50
1 Elfogadva 0/0 3ms 1816 KiB
2 Elfogadva 0/0 29ms 4124 KiB
3 Hibás válasz 0/2 3ms 2268 KiB
4 Elfogadva 2/2 3ms 2464 KiB
5 Elfogadva 2/2 3ms 2636 KiB
6 Hibás válasz 0/2 3ms 2856 KiB
7 Elfogadva 2/2 2ms 2940 KiB
8 Elfogadva 2/2 4ms 3020 KiB
9 Elfogadva 2/2 7ms 3528 KiB
10 Elfogadva 2/2 8ms 3828 KiB
11 Elfogadva 2/2 14ms 4016 KiB
12 Elfogadva 2/2 16ms 4304 KiB
13 Elfogadva 3/3 4ms 3692 KiB
14 Hibás válasz 0/3 4ms 3852 KiB
15 Hibás válasz 0/3 6ms 4256 KiB
16 Hibás válasz 0/3 7ms 4452 KiB
17 Hibás válasz 0/3 14ms 4860 KiB
18 Hibás válasz 0/3 14ms 4924 KiB
19 Elfogadva 3/3 17ms 5432 KiB
20 Elfogadva 3/3 28ms 6132 KiB
21 Elfogadva 3/3 28ms 6280 KiB
22 Elfogadva 3/3 28ms 6272 KiB