图的存储
模板
nsz: 点数目
msz: 边数目
const int nsz=100050,msz=200050;
//edge with weight
struct te{int t,pr,v;}edge[msz]; //无向图: msz*2
int hd[nsz],pe=1;
void adde(int f,int t,int v){edge[++pe]=(te){t,hd[f],v};hd[f]=pe;}
void adddb(int f,int t,int v){adde(f,t,v);adde(t,f,v);}
//without weight
struct te{int t,pr;}edge[msz];
int hd[nsz],pe=1;
void adde(int f,int t){edge[++pe]=(te){t,hd[f]};hd[f]=pe;}
void adddb(int f,int t){adde(f,t);adde(t,f);}
//traversa
#define forg(p,i,v) for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t)
//vector
vector<int> ed[nsz];
void adde(int f,int t){ed[f].push_back(t);}
void adddb(int f,int t){adde(f,t);adde(t,f);}
拓扑排序
拓扑排序 - 维基百科，自由的百科全书:
有向图的拓扑排序是其顶点的线性排序, 使得对于每个有向边 ((u,v)), (u) 在排序中都在 (v) 之前.
注
反图(将图中所有边反向)的拓扑序为原图拓扑序的逆序.
使用 Tarjan 算法对强连通分量缩点后, 强连通分量标号的顺序为拓扑序的逆序.
模板
ts: 拓扑序
int ts[nsz],pt=0;
bool toposort(){
rep(i,1,n)if(in[i]==0)que[++qt]=i,ts[++pt]=i;
while(qh<=qt){
int u=que[qh++];
for(int i=hd[u],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t){
--in[v];
if(in[v]==0)ts[++pt]=v,que[++qt]=v;
}
}
return pt==n;
}