/* 
    Implementing algorithms - tree
    bana - 2007
    
    Task:
      is the given graph tree
    
    Description:
      in the currently model we are gonna check three conditions:
             (1) only one start vertex can be among end vertices  => root exists and this is it
             (2) all edges bind two vertices and only once        => one edge connected to two vertices
             (3) the graph can be traversed                       => complete graph
             
             all of three conditions are filled => the graph is tree
             
    Realization:
        representation of graph:  vector that holds (s,v) pairs (where s - source vertex and v - end vertex)
        input file: first number is number of graphs, number of edges in the given graph, pairs     
    
*/
  
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <set>


using namespace std;

typedef struct pairs{
      int start; 
      int end;            
} my_pairs;


class bool_tree{
      
      public:
         bool_tree(const int& size){ 
                         v = new my_pairs[capacity = size]; 
                         index=0; 
         };
         
         void push(const int& start,const int& end){  v[index].start = start;
                                                      v[index].end = end;
                                                      index++;  
                                                      
                                                      h.insert( start );
                                                      h.insert( end );                                                     
                                                    };
         
         void display(){
                    for(int i=0;i<capacity;i++)
                       cout << "(" << v[i].start << "," << v[i].end << ")" <<endl;
         };
         
         bool endTest(){
              bool l = true;
              for(int i=0;i<capacity;i++){
                for(int j=i+1;j<capacity;j++){
                        if( v[i].end == v[j].end ) l = false;
                }
              }
              return l;
         };
         

/* checking if all vertices are avaiable   */      
         void isAll(int curr){                               
              for(int i=0;i<capacity;i++){                                                    
                      if( curr == v[i].start ){               
                          isAll( v[i].end );
                          g.insert( v[i].end );
                      }
                      g.insert( curr ); 
              }
         };
         
         
         bool isTree(){ 
              if( h.size() == g.size() ) return true;
              else return false;
         };
                      
                      
         int rootTest(){
              bool l          = true;
              int  justnoroot = 0;
              int  t          = 0;
              int  noroots    = 0;
              int  help       = -1;
              
              for(int i=0;i<capacity;i++){
                for(int j=0;j<capacity;j++){
                        if( v[i].start == v[j].end ) justnoroot++; 
                }
                if(justnoroot == 1){ justnoroot=0; noroots++; } 
                   else{
                       if(t == 1){ 
                           if( help != v[i].start){ l = false; }
                       }else{ t=1; help=v[i].start;  }
                   }
              }
              root = help;
              return root;
         };
         
      private:
         set<int> g;
         set<int> h; // elements of graphs because capacity is not always equal to it
         my_pairs *v;
         int capacity;
         int index;
         int root;
                                          
};    


int main(int argc, char *argv[])
{ 
    string filename;
    cout << "Input file:"; cin >> filename;
    ifstream inp(filename.c_str());
    
    if( inp.fail() )
      { 
         cout << "Can not find the file!" << endl;
         char ch; cin >> ch;
         exit(1); 
      }
        
    int n;
    inp >> n;
    
    if(n<1)
       {  
          cout << "Number of tree is zero!" << endl; 
          char ch; cin >> ch; 
          exit(1); 
       }
    
    ofstream out("output.txt");
    int m;
    int s,e;
    
    bool_tree **T;
    T = new bool_tree*[n];
    
    for(int i=0;i<n;i++){           // number of bool_tree objects is n
       inp >> m;
       T[i] = new bool_tree(m);
       for(int j=0;j<m;j++){
              inp >> s;
              inp >> e;
              T[i]->push(s,e);
       }
    }
    
    
    
    for(int j=0;j<n;j++){
            
       //cout << "The " << j+1 << ". input graph is ordered format (s,v):"; 
       //cout << endl;
       //T[j]->display();
       
       if ( T[j]->endTest() ){
             int root = T[j]->rootTest();                   
             if( root != -1 )   T[j]->isAll(root);      //when there is root
       }
       if( T[j]->isTree() ) out << j+1 <<". tree" << endl; 
       else out << j+1 << ". not tree" << endl;
       
    } 
                           
    inp.close(); 
    out.close();
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

