重庆城乡建设网站首页,不需要写代码的网站开发软件,建设局网站安全自查情况报告,万网官网4399正题
题目链接:https://loj.ac/p/2788 题目大意
给出nnn个点mmm条边的一张图#xff0c;求它的所有割边。 1≤n≤105,1≤m≤61061\leq n\leq 10^5,1\leq m\leq 6\times 10^61≤n≤105,1≤m≤6106#xff0c;内存限制16MB 解题思路
我们存不下所有的边#xff0c;但是nnn很…正题
题目链接:https://loj.ac/p/2788 题目大意
给出nnn个点mmm条边的一张图求它的所有割边。
1≤n≤105,1≤m≤6×1061\leq n\leq 10^5,1\leq m\leq 6\times 10^61≤n≤105,1≤m≤6×106内存限制16MB 解题思路
我们存不下所有的边但是nnn很小。一个朴素的想法是我们搞出一棵生成树来然后对于非树边(x,y)(x,y)(x,y)就相当于把xxx到yyy路径上的边都标记成非割边然后剩下的就是割边了。
但是我们不能离线建生成树因为我们存不下所有的边考虑一下别的方向的优化。我们会发现对于非树边来说如果这一条非树边能被其他非树边完全覆盖那么说明这条边就没有用所以我们对于非树边来说也只需要保留一棵最小生成树即可。
然后至于标记方面用树上差分来处理就好了。
时间复杂度O(mnlogn)O(mn\log n)O(mnlogn) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includecctype
using namespace std;
const int N1e510;
int n,m,fa[N],Fa[N],c[N],dep[N],f[N][18];
vectorint G[N];bool v[N];
vectorpairint,int e;
int find(int x)
{return (fa[x]x)?(x):(fa[x]find(fa[x]));}
int Find(int x)
{return (Fa[x]x)?(x):(Fa[x]Find(Fa[x]));}
int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
void dfs(int x,int fa){dep[x]dep[fa]1;v[x]1;for(int i0;iG[x].size();i){int yG[x][i];if(yfa)continue;dfs(y,x);f[y][0]x;}return;
}
void calc(int x,int fa){v[x]1;for(int i0;iG[x].size();i){int yG[x][i];if(yfa)continue;calc(y,x);c[x]c[y];}if(!c[x]fa)printf(%d %d\n,x,fa);return;
}
int LCA(int x,int y){if(dep[x]dep[y])swap(x,y);for(int i17;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i];if(xy)return x;for(int i17;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)fa[i]Fa[i]i;for(int i1;im;i){int xread(),yread();if(find(x)!find(y)){fa[find(x)]find(y);G[x].push_back(y);G[y].push_back(x);}else if(Find(x)!Find(y)){Fa[Find(x)]Find(y);e.push_back(make_pair(x,y));}}for(int i1;in;i)if(!v[i])dfs(i,0);memset(v,0,sizeof(v));for(int j1;j18;j)for(int i1;in;i)f[i][j]f[f[i][j-1]][j-1];for(int i0;ie.size();i){int xe[i].first,ye[i].second;c[x];c[y];c[LCA(x,y)]-2;}for(int i1;in;i)if(!v[i])calc(i,0);return 0;
}
