fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. class Tree{
  8. public:
  9.    int N;
  10.    vector<int> parent;
  11.    vector<vector<int> > child;
  12.  
  13.    Tree():N(0){};
  14.    Tree(int n):N(n){
  15.       parent.resize(N+1,-1);
  16.       child.resize(N);
  17.    }
  18.  
  19.    void print(){
  20.       for(int i=0; i<N+1; i++){
  21.          if(parent[i] != -1)
  22.             printf("%d\n",parent[i]);
  23.       }
  24.    }
  25. };
  26.  
  27. class Graph{
  28. public:
  29.    int N;
  30.    vector<vector<int> > adj;
  31.  
  32.    Graph():N(0){};
  33.    Graph(int n):N(n){adj.resize(N+1);}
  34.  
  35.    void addNode(int x, int y){
  36.       adj[x].push_back(y);
  37.       adj[y].push_back(x);
  38.    }
  39.  
  40.    void sortNode(){
  41.       for(int i=0; i<N+1; i++)
  42.          sort(adj[i].begin(), adj[i].end());
  43.    }
  44.  
  45.    Tree makeTree(int root){
  46.       Tree T(N+1);
  47.       queue<int> q;
  48.       vector<bool> check(N,false);
  49.  
  50.       q.push(root);
  51.       check[root] = true;
  52.  
  53.       while(!q.empty()){
  54.          int cur = q.front();
  55.          q.pop();
  56.  
  57.          for(int next : adj[cur]){
  58.             if(check[next] == false){
  59.                check[next] = true;
  60.                q.push(next);
  61.                T.parent[next] = cur;
  62.                T.child[cur].push_back(next);
  63.             }
  64.          }
  65.       }
  66.       return T;
  67.    }
  68. };
  69.  
  70.  
  71. int main() {
  72.  
  73.    int n;
  74.    scanf("%d",&n);
  75.  
  76.    Graph G(n);
  77.    for(int i=0; i<n; i++){
  78.       int a,b;
  79.       scanf("%d %d",&a,&b);
  80.       G.addNode(a,b);
  81.    }
  82.    G.sortNode();
  83.    Tree T = G.makeTree(1);
  84.    T.print();
  85.  
  86.    return 0;
  87. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
7
1 6
6 3
3 5
4 1
2 4
4 7
stdout
copy 
4
6
1
3
1
4
https://ideone.com/kWB0A9
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!