85482024-01-21 19:33:40qertendKerékpártúra (50 pont)cpp17Accepted 50/50206ms31584 KiB
#include <iostream>
#include <set>
#include <list>
//#include <set>
using namespace std;

bool hasInt(int target, list<int> field) {
    for (int i : field) {
        if (i == target) return true;
    }
    return false;
}

int main()
{
    int numberOfNodes, routes, startID;
    cin >> numberOfNodes;
    cin >> routes;
    cin >> startID;

    struct Node {
        list<int> outgoing;
        list<int> incoming;
        void connected(set<int> &connectedByIncoming, set<int> &connectedByOutgoing,Node nodesList[]) {
            for (int i : incoming) {
                if (connectedByIncoming.end() == connectedByIncoming.find(i)) {
                    connectedByIncoming.insert(i);
                    nodesList[i].connected(connectedByIncoming, connectedByOutgoing, nodesList);
                }
            }
            for (int i : outgoing) {
                connectedByOutgoing.insert(i);
            }
        }
    };
    Node nodes[numberOfNodes];

    //read all routes from stdin
    for (int i = 0; i < routes; i++) {
        int startPoint, endPoint;
        cin >> startPoint;
        cin >> endPoint;
        Node &startNode = nodes[startPoint-1];
        Node &endNode = nodes[endPoint-1];
        startNode.outgoing.push_back(endPoint-1);
        endNode.incoming.push_back(startPoint-1);
    }

    set<int> connectedByIncoming;
    set<int> connectedByOutgoing;
    nodes[startID-1].connected(connectedByIncoming, connectedByOutgoing, nodes);
    connectedByIncoming.merge(connectedByOutgoing);
    connectedByIncoming.erase(startID-1);
    int size = connectedByIncoming.size();
    cout << size << "\n";
    for (int i : connectedByIncoming) {
        cout << i+1 << " ";
    }

    return 0;
}
/**
 * TODO
 * redo with set instead of list
*/
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1812 KiB
2Accepted0/023ms6348 KiB
3Accepted2/23ms2156 KiB
4Accepted2/23ms2356 KiB
5Accepted2/23ms2572 KiB
6Accepted2/23ms2808 KiB
7Accepted2/23ms2900 KiB
8Accepted2/24ms3440 KiB
9Accepted2/24ms3740 KiB
10Accepted2/26ms3976 KiB
11Accepted2/27ms4556 KiB
12Accepted2/216ms6340 KiB
13Accepted2/214ms5872 KiB
14Accepted2/228ms8516 KiB
15Accepted3/341ms11092 KiB
16Accepted4/446ms12136 KiB
17Accepted4/467ms15376 KiB
18Accepted3/365ms14476 KiB
19Accepted3/354ms13476 KiB
20Accepted3/3166ms27240 KiB
21Accepted3/3201ms30788 KiB
22Accepted3/3206ms31584 KiB