建图模板
分别使用点权建图和边权建图 (权值在点上成为点权图 权值在边上称为边权图)
离散化建图和连续点建图(离散化建图一般用于点的范围为1e9 连续点建图点的范围为1e5 可以直接开数组或vector即可)
const int N=1E5+10,M=2E5+10;
vectorg[N]; //领接表的vector写法 仅适用于点权建图
int ne[M],h[N],w[M],e[M],idx;
void add(int a,int b,int c) //领接表的数组形式
{
ne[idx]=h[a],w[idx]=c,e[idx]=b,h[a]=idx++;
}
int n,m;// n个点 m条边
//1.点权建图(权值在节点上)
for(int i=1;i>a>>b;
g[a].push_back(b); // 建一条边: a->b
g[b].push_back(a); //把这句话注释掉就变成有向图(只有a->b这个方向的边)
}
for(int i=1;i>w[i]; //权值在节点上
// 2.边权建图(权值在边上)
// 1.1 连续点建图方式
for(int i=1;i>a>>b>>c;
add(a,b,c); //a->b
add(b,a,c); //b->a
}
//1.2 离散化建图方式 一般点的范围比较大才使用
//3.访问
void dfs(int u,int fa) //如果是有向图 就不需要fa这个变量
{
//do things
for(int &x:g[u]) //访问u的所有节点
{
if(x==fa)continue; //无向边才需要这一句 保证每个节点只会被访问一次(不理解的可以直接背过)
dfs(x,u);
// do things
}
}