首页 > 其他分享 >支持 range-based for 循环的链式前向星模板

支持 range-based for 循环的链式前向星模板

时间:2023-09-10 09:45:39浏览次数:57  
标签:return int graph Iter range based 前向星

众所周知,OI 中图的存储主要有两种方式:使用 std::vector 实现的邻接表,以及链式前向星。前者的常数较大,有时候会出现卡不过去的情况,但是支持 range-based for 循环,遍历的时候代码更简洁。可不可以在使用链式前向星的同时,使用 range-based for 循环呢?如以下代码所示:

Graph graph;
int u;
...
for (v : graph[u]) {
    ...
}

为了支持 range-based for 循环,graph[u] 需要支持 begin()end()。这两个函数的返回值为迭代器,需要重载 != 和前缀 ++ 运算符。我们可以定义一个迭代器类型,内部有指向原图的指针,以及一个整数,表示边的编号。为了方便,graph[u] 的类型也是它,graph[u].begin 的返回值等于 graph[u]

struct Graph {
    int cnt, head[V], nxt[E], to[E];
    struct Iter {
        Iter(Graph *g, int i) : g(g), i(i) {}
        Graph *g;
        int i;
        bool operator!=(Iter &o) { return i != o.i; }
        Iter operator++() {
            i = g->nxt[i];
            return *this;
        }
        int operator*() { return g->to[i]; }
        Iter begin() { return *this; }
        Iter end() { return {g, 0}; }
    };
    Iter operator[](int i) { return {this, head[i]}; }
    void link(int u, int v) {
        nxt[++cnt] = head[u];
        to[cnt] = v;
        head[u] = cnt;
    }
};

标签:return,int,graph,Iter,range,based,前向星
From: https://www.cnblogs.com/dingxutong/p/17690783.html

相关文章

  • SAML-based SSO Flow
    概念SAML:SecurityAssertionMarkupLanguageSSO:singlesign-onSP:ServiceProviderIdP:IdentityproviderUA:UserAgent(Browser)SP-InitiatedSSOFlowTheprocessingisasfollows:1Theuserattemptstoaccessaresourceonsp.example.com.Theuserd......
  • Orange Pi 3B 开发板 开箱评测 和 系统安装教程
    香橙派OrangePi3B(RK3566)开发板开箱测评和系统烧录教程简介香橙派OrangePi3B是一款树莓派大小的单板计算机,但接口更加齐全,包括一个全尺寸HDMI接口和一个M.2存储插槽,售价199起。OrangePi3B采用了瑞芯微RK3566四核64位Cortex-A55处理器,采用的22nm工艺,主频最高......
  • IDEA编译报错:maven-resources-production:guyi-admin: java.lang.IndexOutOfBoundsExc
    编译项目的时候,IDEA一直提示:maven-resources-production:xxxxxx:java.lang.IndexOutOfBoundsException:Range[-1,-1+1025)outofboundsforlength1024,maven-resources-production:xxxxxx:java.lang.IndexOutOfBoundsException:Range[-1,-1+1025)outofboundsfor......
  • Python内置函数 - enumerate, range, max, len
    1, enumerate(可迭代对象,index_base)fromcollections.abcimportIteratormy_list=["aa","b","c"]result=enumerate(my_list)#迭代器:每次返回一个元组,tuple(index,value)print(type(result))#<class'enumerate'>prin......
  • Android官方资料--Block-Based OTAs
    Block-BasedOTAsINTHISDOCUMENTRecommendationsFilevs.BlockOTAsUpdatingunmodifiedsystemsUpdatingmodifiedsystemsYoucanenableblock-basedover-the-air(OTA)updatesfornewdevicesrunningAndroid5.0.OTAisthemechanismbywhichOEMsremote......
  • A Challenge Dataset and Effective Models for Aspect-Based Sentiment Analysis
    摘要基于方面的情感分析(ABSA)由于其广泛的应用,近年来受到了越来越多的关注。在现有的ABSA数据集中,大多数句子只包含一个或多个具有相同情感极性的方面,这使得ABSA任务退化为句子级情感分析。在本文中,我们提出了一个新的大规模多方面多情感(MAMS)数据集,其中每个句子至少包含两个具有不......
  • range 关键字
    packagemainimport"fmt"funcmain(){//创建一个整数数组numbers:=[5]int{10,20,30,40,50}//使用range关键字遍历数组fmt.Println("遍历数组:")forindex,value:=rangenumbers{fmt.Printf("索引%d的值是%d\n",......
  • sql-labs--Less-1--Error based-Single quotes
    sql\="SELECT\*FROMusersWHEREid\='id'LIMIT0,1";打开第一关,我们看到如下界面,上面写着PleaseinputtheIDasparameterwithnumericvalue,它的意思是让我们请输入ID作为带有数值的参数。https://images.cnblogs.com/cnblogs_com/blogs/800546/galleries/2341394/o_2......
  • range方法在Python2和Python3中的不同
    range()方法是Python中常用的方法,但是在Python2和Python3中使用方法不同,下面看下它们的不同使用方法。range方法详解range(start,stop[,step])range是python中的其中一个内置函数作用:可创建一个整数列表。一般用在for循环中。参数说明:start:起点,一般和stop搭配使用,既生成从star......
  • CF838D Airplane Arrangements 题解
    题意一架飞机有\(n\)个座位排成一列,有\(m\)名乘客(\(m\leqn\))依次上飞机。乘客会选择一个目标座位(两人可以选同一个目标座位),然后选择从前门或者后门上飞机,上飞机后,他们会走到自己的目标座位,如果目标座位已经有人坐了,他们会继续往前走,在走到第一个空位后坐下。如果走到最后......