126292024-12-26 23:45:16BucsMateElágazás nélküli úton levő települések (50 pont)cpp17Elfogadva 50/5027ms1336 KiB
#include <iostream>
#include <vector>

using namespace std;

void search_graph(int start, vector<vector<int>> &adj, bool visited[])
{
    int currNode = start;
    int lastNode = -1;
    bool valid = true;
    while(valid){
        if(adj[currNode].size() > 2){
            return;
        }
        valid = false;
        for(int i = 0; i < adj[currNode].size(); i++){
            int newNode = adj[currNode][i];
            if(newNode != lastNode){
                lastNode = currNode;
                currNode = newNode;
                visited[currNode] = true;
                valid = true;
                break;
            }
        }
    }
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int>> adj(N+2, vector<int>());
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    bool visited[10001] = {};
    for(int i = 1; i <= N; i++){
        if(adj[i].size() == 1){
            search_graph(i, adj, visited);
        }
    }

    vector<int> sol;
    for(int i = 1; i <= N; i++){
        if(visited[i]){
            sol.push_back(i);
        }
    }
    cout << sol.size() << endl;
    for(int i = 0; i < sol.size(); i++){
        cout << sol[i] << " ";
    }
    cout << endl;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms500 KiB
2Elfogadva0/027ms1332 KiB
3Elfogadva2/21ms320 KiB
4Elfogadva2/21ms320 KiB
5Elfogadva2/21ms320 KiB
6Elfogadva2/21ms320 KiB
7Elfogadva2/21ms320 KiB
8Elfogadva2/22ms320 KiB
9Elfogadva2/24ms556 KiB
10Elfogadva2/27ms556 KiB
11Elfogadva2/213ms772 KiB
12Elfogadva2/213ms752 KiB
13Elfogadva3/32ms320 KiB
14Elfogadva3/33ms320 KiB
15Elfogadva3/34ms568 KiB
16Elfogadva3/34ms568 KiB
17Elfogadva3/312ms772 KiB
18Elfogadva3/312ms748 KiB
19Elfogadva3/316ms944 KiB
20Elfogadva3/326ms1116 KiB
21Elfogadva3/327ms1336 KiB
22Elfogadva3/327ms1272 KiB