61462023-11-03 21:03:10MrChipserElágazás nélküli úton levő települések (50 pont)cpp11Wrong answer 31/5029ms5844 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 votmazs[n] = {0};
    int zsakfalvak[n] = {0};
    vector<int>zsakok;
    for(int i = 0; i < n; i ++)
    {
        if(adj[i].size()==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;
    int zsakfalu[n] ={0};
    zsakfalu[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++;
                    zsakfalvak[x]=1;
                    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(zsakfalvak[i]==1 && adj[i].size()!=1)
            cout << i+1 << " ";
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base31/50
1Accepted0/03ms1688 KiB
2Accepted0/029ms4160 KiB
3Wrong answer0/22ms2136 KiB
4Accepted2/23ms2344 KiB
5Accepted2/23ms2560 KiB
6Wrong answer0/22ms2676 KiB
7Accepted2/23ms2800 KiB
8Accepted2/24ms2896 KiB
9Accepted2/26ms3120 KiB
10Accepted2/28ms3584 KiB
11Accepted2/214ms3784 KiB
12Accepted2/216ms3972 KiB
13Accepted3/34ms3008 KiB
14Wrong answer0/34ms3344 KiB
15Wrong answer0/36ms3892 KiB
16Wrong answer0/38ms4308 KiB
17Wrong answer0/314ms5004 KiB
18Wrong answer0/314ms5112 KiB
19Accepted3/318ms5288 KiB
20Accepted3/328ms5644 KiB
21Accepted3/329ms5844 KiB
22Accepted3/329ms5804 KiB