198452025-12-25 23:07:48KristófElágazás nélküli úton levő települések (50 pont)cpp17Időlimit túllépés 41/50298ms1920 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())
        {
        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
base41/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/048ms1920 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/22ms500 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/24ms316 KiB
9Elfogadva2/28ms564 KiB
10Elfogadva2/214ms584 KiB
11Elfogadva2/214ms1068 KiB
12Elfogadva2/217ms1116 KiB
13Elfogadva3/37ms316 KiB
14Elfogadva3/325ms544 KiB
15Elfogadva3/390ms740 KiB
16Időlimit túllépés0/3298ms820 KiB
17Elfogadva3/3189ms1164 KiB
18Időlimit túllépés0/3289ms1332 KiB
19Időlimit túllépés0/3216ms1380 KiB
20Elfogadva3/337ms1632 KiB
21Elfogadva3/343ms1864 KiB
22Elfogadva3/354ms1904 KiB