CF732 F Tourist Reform——边双连通分量
2024-09-08 02:45:59
题目:http://codeforces.com/contest/732/problem/F
首先把边双缩点,边双内部 dfs 一个顺序一定是可以从每个点走到边双内部所有点的,因为它是以环为基本单位;
然后对于缩点之后的图,找到 siz 最大的点作为根 dfs,再连反边,那么只有 siz 最大的那个点只能走到自己内部,就可以使答案最大;
结构体要开得精细一点,防止爆空间?还是什么奇奇怪怪的错误之类的...
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=4e5+;
int n,m,hd[maxn],ct=,cnt=,dfn[maxn],low[maxn],tim,col[maxn],cr,siz[maxn];
int sta[maxn],top,head[maxn];
bool vis[maxn];
//struct N{
// int to,nxt,bh,u,v,f;
// N(int t=0,int n=0,int b=0):to(t),nxt(n),bh(b) {}
//}ed[maxn<<1],e[maxn],edge[maxn<<1];//这样写会爆空间?!
struct N{
int to,nxt,bh;
N(int t=,int n=,int b=):to(t),nxt(n),bh(b) {}
}ed[maxn<<],edge[maxn<<];
struct E{int u,v,f;}e[maxn];
void add(int x,int y,int b){ed[++ct]=N(y,hd[x],b); hd[x]=ct;}
void add2(int x,int y,int b){edge[++cnt]=N(y,head[x],b); head[x]=cnt;}
void tarjan(int x,int f)
{
dfn[x]=low[x]=++tim; vis[x]=; sta[++top]=x;
for(int i=hd[x];i;i=ed[i].nxt)
{
int u=ed[i].to;
if(u==f)continue;
if(!dfn[u]) tarjan(u,x),low[x]=min(low[x],low[u]);
else if(vis[u]) low[x]=min(low[x],dfn[u]);
}
if(dfn[x]==low[x])
{
cr++;
while(sta[top]!=x)
{
int y=sta[top]; top--;
vis[y]=; col[y]=cr; siz[cr]++;
}
top--; vis[x]=; col[x]=cr; siz[cr]++;
}
}
void dfs(int x)
{
vis[x]=;
for(int i=head[x],u,eg;i;i=edge[i].nxt)
{
if(vis[u=edge[i].to])continue;
if(x==col[e[eg=edge[i].bh].u]) e[eg].f=;
else e[eg].f=;
dfs(u);
}
}
void dfs2(int x)
{
vis[x]=;
for(int i=hd[x],u,eg;i;i=ed[i].nxt)
{
u=ed[i].to;
if(col[u]!=col[x])continue;
if(x==e[eg=ed[i].bh].u) e[eg].f=;
else e[eg].f=;
if(!vis[u])dfs2(u);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&e[i].u,&e[i].v);
add(e[i].u,e[i].v,i); add(e[i].v,e[i].u,i);
}
for(int i=;i<=n;i++) if(!dfn[i])tarjan(i,);
memset(vis,,sizeof vis);
for(int i=;i<=n;i++) if(!vis[i])dfs2(i);
for(int i=,u,v;i<=ct;i++)
if((u=col[ed[i].to])!=(v=col[ed[i^].to]))add2(u,v,ed[i].bh),add2(v,u,ed[i].bh);
int rt=,mx=;
for(int i=;i<=cr;i++)
if(siz[i]>mx)mx=siz[i],rt=i;
printf("%d\n",mx);
memset(vis,,sizeof vis);
dfs(rt);
for(int i=;i<=m;i++)
{
if(e[i].f==)printf("%d %d\n",e[i].u,e[i].v);
else printf("%d %d\n",e[i].v,e[i].u);
}
return ;
}
最新文章
- Eclipse开发工具组合键介绍
- mysql日期格式化
- 勇者斗恶龙UVa11292 - Dragon of Loowater
- ios8版本地图定位注意点
- CSS用类选择器在本页写样式
- swift 开眼今日精选
- PHP 各种函数
- CSS注释代码
- Leetcode_Best Time to Buy and Sell Stock
- Centos7系统配置上的变化(三)为网络接口添加多IP
- hdu 3006	 The Number of set
- How to use data analysis for machine learning (example, part 1)
- 如何使用MVP+Dagger2+RxJava+Retrofit开发(1)
- Ransom Note(383)
- 编译、裁剪、安装、删除 Ubuntu内核和模块管理
- git与eclipse集成之创建及切换个人本地分支
- try与except处理异常语句
- LInux下设置账号有效时间 以及 修改用户名(同时修改用户组名和家目录)
- 【eclipse jar包】在编写java代码时,为方便编程,常常会引用别人已经实现的方法,通常会封装成jar包,我们在编写时,只需引入到Eclipse中即可。
- org.hibernate.AssertionFailure: null id in xxx.xx.xx的问题