Just CS rookie practice on DFS\BFS. But details should be taken care of:

1. Ruby implementation got TLE so I switched to C++

2. There's one space after each output node, including the last one. But SPOJ doesn't clarify it clearly.

// 442#include 
      
       #include 
       
        #include 
        

> Graph;void bfs(Graph &g, int key){ vector

visited; visited.reserve(g.size()); for(unsigned ic = 0; ic < g.size(); ic ++) { visited[ic] = 0; } queue

fifo; fifo.push(key); while(!fifo.empty()) { int cKey = fifo.front(); fifo.pop(); if(visited[cKey - 1] == 0) { cout << cKey <<" "; vector

&ajVec = g[cKey]; for(unsigned i = 0; i < ajVec.size(); i ++) { fifo.push(ajVec[i]); } visited[cKey - 1] = 1; } } cout << endl;}vector

dfs_rec;void initDfsRec(Graph &g){ dfs_rec.clear(); unsigned gSize = g.size(); dfs_rec.reserve(gSize); for(unsigned ic = 0; ic < gSize; ic ++) { dfs_rec[ic] = 0; }}void dfs(Graph &g, int key){ cout << key << " "; dfs_rec[key - 1] = 1; vector

&ajVec = g[key]; for(unsigned i = 0; i < ajVec.size(); i ++) { if(dfs_rec[ajVec[i] - 1] == 0) { dfs(g, ajVec[i]); } }}int main(){ int runcnt = 0; cin >> runcnt; for(int i = 0; i < runcnt; i ++) { Graph g; int nvert = 0; cin >> nvert; for(int n = 0; n < nvert; n ++) { int vid = 0; cin >> vid; int cnt = 0; cin >> cnt; vector

ajVec; for(int k = 0; k < cnt; k ++) { int aj = 0; cin >> aj; ajVec.push_back(aj); } g.insert(Graph::value_type(vid, ajVec)); } // cout << "graph " << i +1 << endl; int ikey = 0, iMode = 0; cin >> ikey >> iMode; while(!(ikey == 0 && iMode == 0)) { if(iMode == 0) { initDfsRec(g); dfs(g, ikey); cout <

> ikey >>iMode; } } return 0;}