二分图
染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图 时间复杂度是 O(n+m)O(n+m)O(n+m), nnn 表示点数，mmm 表示边数 123456789101112131415161718192021222324bool dfs(int u,int c){//判断存在奇环，存在返回true color[u]=c; for(auto v:e[u]){ if(!color[v]){ if(dfs(v,3-c))return 1; } else if(color[v]==c)return 1;//有奇环 } return 0;}bool check(){//判断是不是二分图 fill(color,color+1+n,0); bool flag = true; for (int i = 1; i <= n; i ++ )//可能图不连通 if (!color[i] ) if...
欧拉路
欧拉路 构造题中的欧拉回路 | tyqtyq 的博客 2018的国家集训队论文《欧拉图相关的生成与计数问题探究》 [Tricks] 记各类欧拉回路问题 - 樱雪喵 - 博客园 欧拉路径是满足恰经过所有边一次的通路 欧拉回路是起点和终点相同的一条欧拉路径. 判别法则： 有向图存在欧拉回路: G中所有度数非0的点是强连通的，且所有点入度均等于出度. 有向图存在欧拉通路: 将边看成无向边后，G中所有度数非0的点是连通的。 最多只有一个点入度比出度大 1，作为欧拉通路的起点 最多只有一个点出度比入度大 1，作为欧拉通路的终点 其他所有点入度均等于出度 无向图存在欧拉回路: G中所有度数非0的点是连通的且所有点度数均为偶数. 无向图存在欧拉通路: G中所有度数非0的点是连通。并且G中恰好存在0或2个奇度点。 其他所有点度数均为偶数。那两个奇度点中, 一个作为欧拉通路之起点, 另一个作为终点. 算法流程：感性理解：先找一条起点到终点的通路，然后不断回溯找环。 先用充要条件也就是度数和连通性去判断是不是存在欧拉路...
判负环——spfa
单测试点有多组测试数据，注意fill手动清空 1234567891011121314151617181920212223242526272829303132333435int e[M],ne[M],w[M],h[N],idx;int d[N],cnt[N],vis[N];//为了卡常用spfa的时候就用链式前向星void init(){ fill(h,h+n+1,-1);idx=0;}void add(int a,int b,int c){//调用之前h要全部变成-1 e[idx]=b;w[idx]=c; ne[idx]=h[a];h[a]=idx++;}bool spfa(){ //判负环，存在返回true fill(d,d+n+1,inf); fill(vis,vis+n+1,0); fill(cnt,cnt+n+1,0); queue<int>q; for(int i=1;i<=n;i++) { q.push(i); vis[i]=true;...
强连通分量
scc：极大的强连通子图（两两相互可达） 123456789101112131415161718192021222324252627282930313233343536373839404142const int N=10010;int n,m,a,b;vector<int> e[N]; int dfn[N],low[N],tot;int stk[N],instk[N],top;int scc[N],siz[N],cnt;void tarjan(int x){ //入x时，盖戳、入栈 dfn[x]=low[x]=++tot; stk[++top]=x,instk[x]=1; for(int y : e[x]){ if(!dfn[y]){//若y尚未访问 tarjan(y); low[x]=min(low[x],low[y]);//回x时更新low } else if(instk[y])//若y已访问且在栈中 ...
图论一般题合集
病毒溯源 题意：给定一棵树，求出最大深度，要求输出字典序最小的路径 Solution:由于看错题，以为是dag，然后发现只需要拓扑排序一下然后dp最长路就可以了。但值得注意的是需要提前对邻接表排序保证字典序，每次更新都需要维护终点，必须在过程中维护。我们找的是后缀最大值，但希望前缀结构最小。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263vector<int>e[N];int din[N];vector<int>tp;vector<int>dp(N+1,0);void topsort(){ queue<int>q; for(int i=0;i<=n-1;i++)if(din[i]==0){q.push(i);dp[i]=1;} while(q.size()){ auto...
最短路计数
P1144 最短路计数 题意：求出起点到各个点的最短路条数。 Solution：在堆优化dij的过程中维护每个点的最短路条数数组，如果严格小于就赋值，如果等于就累加 1234567891011121314151617181920212223242526272829303132333435363738struct edge{int v,w;};vector<edge>e[N];void add(int u,int v,int w){ e[u].push_back({v,w});}void solve(){ cin>>n>>m; for(int i=1;i<=m;i++){ int...
Codeforces Round 923 (Div. 3)
Codeforces Round 923 (Div. 3) F：给定一张一般图，不保证连通，定义一个简单环的权值是环中最小边的权值，求图中最小环的权值和具体由哪些点组成。 Sol：首先需要思考的是怎么求出最大权值？我们考虑用克鲁斯卡尔算法的思想对边权排序，考虑逐步加入图中，一旦合并失败就说明当前边构成了这个环的最小边，我们维护答案，同时记录左右端点。 第二阶段我们需要利用最小边的两个点把目标环的所有点找出来。我们用标记数组保证点不走回头路，用flag保证函数递归栈退出，不再执行循环。从L开始dfs，遇到R的时候就统计答案。 实现的地方还有一个困难就是对于不在环上的点可能需要加入再删除，这样比较啰嗦，提供一种jly用bool返回值的写法。当更深的递归函数返回结果时，当前的点才加入path中 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455//为了给小的边机会，我们当然应该将边权从大到小加进图中struct...
SPFA
SPFA 最短路:保证数据不存在负环的情况下，求1-n最短路 12345678910111213141516171819202122232425262728293031323334353637383940414243struct edge { int v, w;};void solve() { int n, m; cin >> n >> m; vector<vector<edge>> e(n + 1); for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; e[u].push_back({v, w}); } vector<int> dis(n + 1, inf); auto spfa = [&]() { ...
倍增求lca
倍增求lca 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748struct edge{ int v,w;};//思考：要想知道一个数有几个二级制位，直接n=__lg(x)//我们可以知道<n最近的2的次幂，9最大的是8，8虽然是2的3次方，但要遍历它的每一位//需要3到0开始，也就是考虑到0的影响，我们可以正好满足偏移。//2的3次方有四位，也就是__lg(x)就是我们需要的最高位，从它开始往低遍历vector<edge>e[N];int dep[N];int d[N];const int len=__lg(N);int f[N][len+2];int cnt[N];int ans=0;void dfs(int u,int fa){ dep[u]=dep[fa]+1; f[u][0]=fa; for(int...
常用树上函数
常用树上函数 给定k个点·，判断他们能不能被同一条链覆盖。（也就是能不能构成简单路径） Sol:找到链的两个端点p1,p2，链上的点x一定满足lca(p1,x)=x,lca(p2,x)=lca(p1,p2)lca(p1,x)=x,lca(p2,x)=lca(p1,p2)lca(p1,x)=x,lca(p2,x)=lca(p1,p2)或者lca(p2,x)=x,lca(p1,x)=lca(p1,p2)lca(p2,x)=x,lca(p1,x)=lca(p1,p2)lca(p2,x)=x,lca(p1,x)=lca(p1,p2) 1234567891011121314151617181920212223242526272829auto checkchain = [&](vector<int> &node) { int p1 = 0, p2 = 0; deb(lcarmq.dep); for (auto x : node) { if (p1 == 0 ||...
最新文章