图的存储方式之前向星与邻接表

//前向星
struct graph{
    typedef vector<int> VI;
    VI info,next,to;
    //假设现在有n个点，m条边,info长度为n，next和to长度为m。
    //其中，info保存着所有节点的第一个边
    //next保存着所有边信息的下一个边
    //to保存着边的下一个节点信息。如果是带权边，可以增加一个weights数组，与to类似。（所有边增加主要加的是to）
    graph(int n=0,int m=0):to(0),next(0){
        info.resize(n);
        next.reserve(m);
        to.reserve(m);
    }

    int edge_size(){
        return to.size();//显然，to即保存了所有边的信息
    }
    int vertex_size(){
        return info.size();//info保存了所有节点的信息
    }
    void expand(int i){
        if(info.size()<i+1)
            info.resize(i+1);
    }
    void add(int i,int j){//添加一条从i到j的边，有向
        expand(i),expand(j);
        to.push_back(j);//压入新边的信息
        next.push_back(info[i]);//新头的下一个指向原来的指针
        info[i] = to.size()-1;//链表头指针指向新加项目
    }
    void del_back(){
        for(int i=0;i<info.size();i++){
            if(info[i] == to.size()-1){
                info[i] = next.back();
                break;
            }
        }
        to.pop_back();
        next.pop_back();
    }
    void clear(){
        info.clear();
        next.resize(0);
        to.resize(0);
    }
};

struct Edge{
    int from,to,weight;
};
vector<Edge> G[maxn];//可以用来模拟邻接表
//使用的时候给对应的数组G[node]插入边即可，其实也挺方便的