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