因為知道了算法tag，所以想到了正解：

先給出兩個性質：

邊雙給邊定向一定可以轉為強連通圖,此為最優解

樹給邊定向后R的最小值必為0

性質2證明如下：

設樹有n個節點, 若R_min!=0, 則每點出度至少為1,各點出度之和至少為n, 則至少有n條邊,但樹只有n-1條邊,矛盾

那么這道題只要在原圖上把邊雙縮成點即可

問題是如何構造？

要解決樹的構造很簡單，因為樹上必有一點無法到達其它節點，而我們又要令R_min最大，那么就令這個無法到達其它節點的點為 包含點的個數最多的邊雙 代表的點 ，把這個點當做 根節點 dfs這棵樹，把樹上的邊（原圖上的橋）定向為 son—>fa，可以保證R_min=根節點代表的邊雙包含點的個數

然后就是我想不到的了，邊雙內部要如何構造呢？

雖然我自己想了一種構造方法，但是T得十分慘烈……

然后，第二天我去學習了dfs樹，發現這個問題變得很簡單

這是我最后用的構造方案：

void dfs(int u){vis[u]=1;for(int i=head[u];i!=-1;i=edge_nxt[i]){int v=edge_v[i];if(edge_br[i]){add_e(edge_u[i],edge_v[i],edge_id[i]);continue;}if(!aa[edge_id[i]]) aa[edge_id[i]]=u,bb[edge_id[i]]=v;//加判斷是為了防止將定好向的(fa[u],u)邊再反向 if(!vis[v]) dfs(v);} }

為什么可行？

用dfs樹理解，這個構造方案就是將所有樹邊定向向下并將所有回邊定向向上，由dfs樹的性質知這一定可行

最后放上完整代碼：

#include<iostream> #include<cstring> #include<cstdio> #include<stack> using namespace std; const int N=4e5+5; int edge_u[N<<1],edge_v[N<<1],edge_id[N<<1],edge_nxt[N<<1],edge_br[N<<1]; int n,m,head[N],cnt,a[N],b[N],aa[N],bb[N]; int dfn[N],low[N],ind,bcc[N],Bcc,bcc_sz[N]; stack<int> s; void add_edge(int u,int v,int id){edge_u[cnt]=u;edge_v[cnt]=v;edge_id[cnt]=id;edge_nxt[cnt]=head[u];head[u]=cnt++; } void tarjan(int u,int fa){dfn[u]=low[u]=++ind;s.push(u);for(int i=head[u];i!=-1;i=edge_nxt[i]){int v=edge_v[i];if(!dfn[v]){tarjan(v,u);low[u]=min(low[u],low[v]);if(low[v]>dfn[u]){edge_br[i]=1;edge_br[i^1]=1;Bcc++;int k;do{k=s.top();s.pop();bcc[k]=Bcc;bcc_sz[Bcc]++;}while(k!=v);}}else{if(dfn[v]<dfn[u]&&v!=fa)low[u]=min(low[u],dfn[v]);}}//勿忘考慮u為根的情況: if(!fa){Bcc++;while(!s.empty()){bcc[s.top()]=Bcc;bcc_sz[Bcc]++;s.pop();}} } int e_u[N<<1],e_v[N<<1],e_id[N<<1],e_nxt[N<<1]; int hd[N],ct; void add_e(int u,int v,int id){e_u[ct]=u;e_v[ct]=v;e_id[ct]=id;e_nxt[ct]=hd[bcc[u]];//highlighthd[bcc[u]]=ct++;//highlight } int num,maxn=0; bool vis_bcc[N],vis[N]; void dfs(int u){vis[u]=1;for(int i=head[u];i!=-1;i=edge_nxt[i]){int v=edge_v[i];if(edge_br[i]){add_e(edge_u[i],edge_v[i],edge_id[i]);continue;}if(!aa[edge_id[i]]) aa[edge_id[i]]=u,bb[edge_id[i]]=v;//加判斷是為了防止將定好向的(fa[u],u)邊再反向 if(!vis[v]) dfs(v);} } void dfs2(int u,int fa){for(int i=hd[u];i!=-1;i=e_nxt[i]){int v=bcc[e_v[i]];if(v==fa) continue;aa[e_id[i]]=e_v[i],bb[e_id[i]]=e_u[i];dfs2(v,u);} } int main(){memset(head,-1,sizeof(head));memset(hd,-1,sizeof(hd));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&a[i],&b[i]);add_edge(a[i],b[i],i);add_edge(b[i],a[i],i);}for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i,0);for(int i=1;i<=n;i++){if(!vis_bcc[bcc[i]]){dfs(i);vis_bcc[bcc[i]]=1;if(bcc_sz[bcc[i]]>maxn){maxn=bcc_sz[bcc[i]];num=bcc[i];}}}dfs2(num,0);printf("%d\n",maxn);for(int i=1;i<=m;i++){if(aa[i]&&bb[i]) printf("%d %d\n",aa[i],bb[i]);else printf("%d %d\n",a[i],b[i]);}return 0; }

總結

以上是生活随笔為你收集整理的CF732F Tourist Reform（dfs树、边双连通图、tarjan）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。