198482025-12-25 23:09:57KristófElágazás nélküli úton levő települések (50 pont)cpp17Accepted 50/5028ms1332 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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/028ms1132 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/21ms316 KiB
7Accepted2/21ms316 KiB
8Accepted2/23ms316 KiB
9Accepted2/24ms564 KiB
10Accepted2/27ms564 KiB
11Accepted2/214ms752 KiB
12Accepted2/214ms660 KiB
13Accepted3/32ms436 KiB
14Accepted3/34ms684 KiB
15Accepted3/34ms564 KiB
16Accepted3/34ms664 KiB
17Accepted3/312ms752 KiB
18Accepted3/313ms860 KiB
19Accepted3/317ms912 KiB
20Accepted3/328ms1100 KiB
21Accepted3/328ms1284 KiB
22Accepted3/328ms1332 KiB