178622025-09-19 20:28:11KristófElágazás nélküli úton levő települések (50 pont)cpp17Hibás válasz 31/5028ms1332 KiB
#include <iostream>
#include <vector>
#include <set>

using namespace std;

void solver(vector <bool> &visit,int s,vector<vector<int>> &graph,set<int> &ans)
{
if(graph[s].size()==2)
    {
    ans.insert(s);
    visit[s]=true;
    for(auto x : graph[s])
        {
        if(!visit[x])
            solver(visit,x,graph,ans);
        }
    }
else
    {
    visit[s]=true;
    ans.insert(s);
    }


}



int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> graph(n+1);
    int tmp1,tmp2;
    for(int i=0;i<m;i++)
        {
        cin>>tmp1>>tmp2;
        graph[tmp1].push_back(tmp2);
        graph[tmp2].push_back(tmp1);
        }
    vector<int> ends;
    for(int i=1;i<=n;i++)
        {
        if(graph[i].size()==1)
            {
            ends.push_back(i);
            }
        }
  //  for(auto x : ends)
  //      {
   //     cout<<x<<" ";
   //     }
   vector<bool> visit(n+1,false);
   set<int> ans;
   for(auto i : ends)
    {
    if(!visit[i])
        {
        visit[i]=true;
        if(!visit[graph[i][0]])
            {
            solver(visit,graph[i][0],graph,ans);
            }

        }
    }
   cout<<ans.size()<<endl;
   for(auto x : ans)
    {
    cout<<x<<" ";
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base31/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/028ms1332 KiB
3Hibás válasz0/21ms508 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Hibás válasz0/21ms316 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/23ms432 KiB
9Elfogadva2/24ms520 KiB
10Elfogadva2/28ms644 KiB
11Elfogadva2/214ms820 KiB
12Elfogadva2/214ms876 KiB
13Elfogadva3/32ms316 KiB
14Hibás válasz0/33ms316 KiB
15Hibás válasz0/34ms564 KiB
16Hibás válasz0/34ms564 KiB
17Hibás válasz0/313ms840 KiB
18Hibás válasz0/313ms856 KiB
19Elfogadva3/317ms832 KiB
20Elfogadva3/328ms1136 KiB
21Elfogadva3/328ms1132 KiB
22Elfogadva3/328ms1332 KiB