题目: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 ;
}

最新文章

  1. Eclipse开发工具组合键介绍
  2. mysql日期格式化
  3. 勇者斗恶龙UVa11292 - Dragon of Loowater
  4. ios8版本地图定位注意点
  5. CSS用类选择器在本页写样式
  6. swift 开眼今日精选
  7. PHP 各种函数
  8. CSS注释代码
  9. Leetcode_Best Time to Buy and Sell Stock
  10. Centos7系统配置上的变化(三)为网络接口添加多IP
  11. hdu 3006 The Number of set
  12. How to use data analysis for machine learning (example, part 1)
  13. 如何使用MVP+Dagger2+RxJava+Retrofit开发(1)
  14. Ransom Note(383)
  15. 编译、裁剪、安装、删除 Ubuntu内核和模块管理
  16. git与eclipse集成之创建及切换个人本地分支
  17. try与except处理异常语句
  18. LInux下设置账号有效时间 以及 修改用户名(同时修改用户组名和家目录)
  19. 【eclipse jar包】在编写java代码时,为方便编程,常常会引用别人已经实现的方法,通常会封装成jar包,我们在编写时,只需引入到Eclipse中即可。
  20. org.hibernate.AssertionFailure: null id in xxx.xx.xx的问题

热门文章

  1. Redis系列(九)--几道面试题
  2. java几种连接数据库的方法
  3. UVA-127 &quot;Accordian&quot; Patience(模拟)
  4. js的title提示
  5. 08 Python基础数据结构
  6. Python基础-获取当前目录,上级目录,上上级目录
  7. SERE0014: Illegal HTML character: decimal 154
  8. Spring整合Junit框架
  9. Spring核心技术(三)——Spring的依赖及其注入(续)
  10. lombok 插件安装