hihoCoder #1183 : 连通性一·割边与割点（求割边与各点模板）
#1183 : 連通性一·割邊與割點
描述
還記得上次小Hi和小Ho學校被黑客攻擊的事情么，那一次攻擊最后造成了學校網絡數據的丟失。為了避免再次出現這樣的情況，學校決定對校園網絡進行重新設計。
學校現在一共擁有N臺服務器(編號1..N)以及M條連接，保證了任意兩臺服務器之間都能夠通過連接直接或者間接的數據通訊。
當發生黑客攻擊時，學校會立刻切斷網絡中的一條連接或是立刻關閉一臺服務器，使得整個網絡被隔離成兩個獨立的部分。
舉個例子，對于以下的網絡：
每兩個點之間至少有一條路徑連通，當切斷邊(3,4)的時候，可以發現，整個網絡被隔離為{1，2，3}，{4，5，6}兩個部分：
若關閉服務器3，則整個網絡被隔離為{1，2}，{4，5，6}兩個部分：
小Hi和小Ho想要知道，在學校的網絡中有哪些連接和哪些點被關閉后，能夠使得整個網絡被隔離為兩個部分。
在上面的例子中，滿足條件的有邊(3,4)，點3和點4。
輸入
第1行：2個正整數，N,M。表示點的數量N，邊的數量M。1≤N≤20,000, 1≤M≤100,000
第2..M+1行：2個正整數，u,v。表示存在一條邊(u,v)，連接了u,v兩臺服務器。1≤u<v≤N
保證輸入所有點之間至少有一條連通路徑。
輸出
第1行：若干整數，用空格隔開，表示滿足要求的服務器編號。從小到大排列。若沒有滿足要求的點，該行輸出Null
第2..k行：每行2個整數，(u,v)表示滿足要求的邊，u<v。所有邊根據u的大小排序，u小的排在前，當u相同時，v小的排在前面。若沒有滿足要求的邊，則不輸出
代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int N=5e4+; struct node{
int u,v;
node(int u,int v):u(u),v(v){}
};
vector<int>v[N];
set<int>ans1;
vector<node>ans2;
int n,m,cnt; //cnt為dfs序
int low[N],dfn[N];
bool vis[N]; void init(){
cnt=;
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(vis,false,sizeof(vis));
ans2.clear();
ans1.clear();
for(int i=;i<=n;i++) v[i].clear();
} void gd_and_gb(int u,int f){
vis[u]=true;
low[u]=dfn[u]=++cnt;
int child=;
for(int i=;i<v[u].size();i++){
int t=v[u][i];
if(!vis[t]){
child++;
gd_and_gb(t,u);
low[u]=min(low[u],low[t]);
if(dfn[u]<=low[t]&&f!=-) //判斷割點條件,可能進入多次，用set
ans1.insert(u);
if(dfn[u]<low[t]) //判斷割邊條件
ans2.push_back(node(min(u,t),max(u,t))); }
else if(t!=f) low[u]=min(low[u],dfn[t]);
}
if(f==-&&child>) ans1.insert(u); //根節點若兒子（不相連）數大于1，則為割點
} bool cmp(node a,node b){
return a.u==b.u?a.v<b.v:a.u<b.u;
} int main(){
while(~scanf("%d%d",&n,&m)){
init();
for(int i=;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
gd_and_gb(,-);
sort(ans2.begin(),ans2.end(),cmp);
if(ans1.size()==)
puts("Null");
else{
for(auto it=ans1.begin();it!=ans1.end();it++)
printf("%d ",*it);
printf("\n");
}
for(int i=;i<ans2.size();i++){
printf("%d %d\n",ans2[i].u,ans2[i].v);
}
}
return ;
}
總結
以上是生活随笔為你收集整理的hihoCoder #1183 : 连通性一·割边与割点（求割边与各点模板）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Spatial Pyramid Pool
- 下一篇： U3D学习13-数据存储