net-姜.cpp

设计一个算法

//利用链接矩阵,深度优先遍历 

#include<iostream>
#include<fstream>

class Node;
class List{
    private:
        Node *table;
        int n;
    public:
        List(int max);        
        ~List();
        void Insert(int i,int j);
        void DFS(Node &);
        int travel();        
};
class Tr_Node{
    private:
        int vertex;
        Tr_Node *next;
    public:
        friend class Node;
        friend class List;
        friend void List::DFS(Node &);
};
class Node{
    private:
        bool visited;
        Tr_Node *next;
    public:
        void Insert(int v);
        friend class List;
}; 
void Node::Insert(int v)
{
	Tr_Node *newnode=new Tr_Node;
	newnode->vertex=v;
	newnode->next=next;
	next=newnode;	
}
void List::DFS(Node &node)
{
     Tr_Node *p=node.next;
     node.visited=true;
     while(p){         
         if(!table[p->vertex].visited){             
             DFS(table[p->vertex]);
         }
         p=p->next;
     }
 }    
List::List(int max)
{
    n=max;
    table=new Node[max];
    for(int i=0;i<n;i++){
        table[i].visited=false;
        table[i].next=0;
    }    
}
   
List::~List()
{   
    Tr_Node *p,*temp;
    for(int i=0;i<n;i++){
        p=table[i].next;
        while(p){
            temp=p;
            p=p->next;
            delete temp;
        }        
    }
    delete []table;
}
void List::Insert(int i,int j)
{            
    table[i].Insert(j);
    table[j].Insert(i);
}
int List::travel()
{
    int count=0;
    for(int i=0;i<n;i++){
        if(!table[i].visited){
            count++;
            DFS(table[i]);
        }
    }
    return count;
}
int main()
{
    using namespace std;
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    if(!fin.is_open()){
        fout<<"the input.txt is not exist."<<endl;
        exit(1);
    }    
    int n,k;
    while(fin>>n>>k){
        List list(n);
        int i,j;
        for(int t=0;t<k;t++){
            fin>>i>>j;
            list.Insert(i-1,j-1);
        }
        fout<<list.travel()<<endl;
    }
    fin.close();
    fout.close();
    return 0;
}