198472025-12-25 23:09:02KristófElágazás nélküli úton levő települések (50 pont)cpp17Hibás válasz 28/50298ms1864 KiB
#include <iostream>
#include <vector>
#include <queue>
using namespace std;



void bfs(vector<vector<int>> adj,int start,vector<bool> &dvisited)
{
vector<bool> visited(adj.size()+1,false);
queue<int> q;
q.push(start);
visited[start]=true;
while(q.size())
    {
    int u=q.front();q.pop();
    for(int x:adj[u])
        {
        if(adj[x].size()>2)
            {
            visited[x]=1;
            dvisited[x]=1;
            continue;
            }
        if(!visited[x])
            {
            q.push(x);
            visited[x]=true;
            dvisited[x]=true;
            }

        }
    }
}



int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n+1);
    int from,to;
    for(int i=0;i<m;i++)
        {
        cin>>from>>to;
        adj[from].push_back(to);
        adj[to].push_back(from);
        }
    queue<int> q;
    vector<bool> visited(n+1,false);
    for(int i=1;i<=n;i++)
        {
        if(adj[i].size()==1){q.push(i);/*visited[i]=true;*/}
        }
    while(q.size())
        {
        if(!visited[q.front()])
            bfs(adj,q.front(),visited);
        q.pop();
        }
    int cnt=0;
    for(int i=1;i<=n;i++)
        {
        if(visited[i])
            cnt+=visited[i];
        }

    cout<<cnt<<"\n";
    for(int i=1;i<=n;i++)
        {
        if(visited[i])
            cout<<i<<" ";
        }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base28/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/046ms1864 KiB
3Hibás válasz0/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Hibás válasz0/21ms344 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/24ms316 KiB
9Elfogadva2/28ms664 KiB
10Elfogadva2/214ms812 KiB
11Elfogadva2/214ms1076 KiB
12Elfogadva2/217ms1136 KiB
13Elfogadva3/37ms420 KiB
14Hibás válasz0/324ms564 KiB
15Hibás válasz0/386ms532 KiB
16Időlimit túllépés0/3298ms820 KiB
17Hibás válasz0/3187ms1164 KiB
18Időlimit túllépés0/3286ms1344 KiB
19Időlimit túllépés0/3215ms1332 KiB
20Elfogadva3/335ms1628 KiB
21Elfogadva3/341ms1864 KiB
22Elfogadva3/352ms1864 KiB