P6954 [NEERC 2017] Connections 题解

P6954 [NEERC 2017] Connections 题解

题目链接

我的博客

前言

本篇总结：清空！

思路

因为删边之后还需要保证所有强连通关系不变，所以我们可以想到所有强连通分量之间的边一定可以删除。

接下来我们考虑如何删除保留一个强连通分量里面的边。

对于有向图来说，\(n\) 个结点强连通需要保证有不超过 \(2n\) 条边。

因此可以在一个强连通分量里面随意找一个点，对它跑一遍正图，一遍反图。（即跑内向树和外向树），保留所有树边。

最后如果删除的边还不满 \(2n\) 条，那么随便选没有被保留的边，直到满 \(2n\) 条边。

警示后人

多测一定要全部清空啊！！！包括 tarjan 的各种数组，最终的标记数组，以及存边的数组！

代码

const int N=1e5+10;
int T,n,m;
int out[N],tot;
//out：是(0)否(1)输出 i 边
//tot：保留的边的个数
struct edge{int nxt[N],to[N];int head[N],num_Edge=0;void add_Edge(int from,int t){nxt[++num_Edge]=head[from];to[num_Edge]=t;head[from]=num_Edge;}void clear(){//清空！for(int i=0;i<N-5;i++) head[i]=0;num_Edge=0;}
}e1,e2;
//e1：正向图，e2：反向图//tarjan板子
int dfn[N],low[N],dfscnt=0;
int scc[N],sc=0,st[N],top=0;
bool vis[N];
//以上的数组都需要清空！！！
void tarjan(int u){dfn[u]=low[u]=++dfscnt;st[++top]=u;vis[u]=1;for(int i=e1.head[u];i;i=e1.nxt[i]){int v=e1.to[i];if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(vis[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){sc++;while(st[top]!=u&&top){scc[st[top]]=sc;vis[st[top]]=0;top--;}scc[st[top]]=sc;vis[st[top]]=0;top--;}
}
//内向树
void dfs1(int u){vis[u]=1;for(int i=e1.head[u];i;i=e1.nxt[i]){int v=e1.to[i];if(vis[v]) continue;if(scc[v]==scc[u]) {out[i]=1;dfs1(v);}} 
}
//外向树
void dfs2(int u){vis[u]=1;for(int i=e2.head[u];i;i=e2.nxt[i]){int v=e2.to[i];if(vis[v]) continue;if(scc[u]==scc[v]) {out[i]=1;dfs2(v);}}
}
void init(){e1.clear();e2.clear();for(int i=0;i<N-5;i++) out[i]=0;tot=0;	for(int i=1;i<=n;i++){dfn[i]=low[i]=0;scc[i]=0;}//尤其不要忘了这三个变量清空！sc=0;dfscnt=0;top=0;
}
void solve(){init();n=Read();m=Read();for(int i=1;i<=m;i++){int x=Read(),y=Read();e1.add_Edge(x,y);e2.add_Edge(y,x);}for(int i=0;i<N-5;i++) vis[i]=0;//每次用之前清空！！for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}for(int i=0;i<N-5;i++) vis[i]=0;for(int i=1;i<=n;i++){if(!vis[i]) dfs1(i);}for(int i=0;i<N-5;i++) vis[i]=0;for(int i=1;i<=n;i++){if(!vis[i]) dfs2(i);}for(int i=1;i<=m;i++) if(out[i]) tot++;for(int i=1;i<=m;i++){if(out[i]) continue;if(tot<2*n) out[i]=1,tot++;//如果不满 2n 条边}
//	puts("----");for(int i=1;i<=m;i++){if(out[i]) continue;printf("%d %d\n",e2.to[i],e1.to[i]);}
}
signed main(){T=Read();while(T--){solve();//多测函数好！}return 0; 
}