HihoCoder 1183 : 連通性一·割邊與割點（模闆）

連通性一·割邊與割點

時間限制:10000ms

單點時限:1000ms

記憶體限制:256MB

描述

還記得上次小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小的排在前面。若沒有滿足要求的邊，則不輸出

樣例輸入

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6      

樣例輸出

3 4
3 4      

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
int const maxn=10010;
int const maxm=200010;
int low[maxn],dfn[maxn],times;
int Laxt[maxn],Next[maxm],To[maxm],cnt;
int cut_num,node[maxn];
bool NUll=true;

struct in{
    int x,y;
}s[maxm];//割邊

bool cmp(in a ,in b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

void add(int u,int v)
{
    Next[++cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
}

int dfs(int u,int pre)
{
    int son=0;
    dfn[u]=low[u]=++times;
    for(int i=Laxt[u];i;i=Next[i]){
        if(To[i]==pre) 
               continue;//不然自環了 
        if(!dfn[To[i]]){
            son++;
            dfs(To[i],u);
            low[u]=min(low[u],low[To[i]]);
            if(dfn[u]<low[To[i]]){//割邊 
                s[++cut_num].x=min(u,To[i]);
                s[cut_num].y=max(u,To[i]);
            }
            if(u!=pre&&dfn[u]<=low[To[i]]){//非根割點 
                NUll=false;
                node[u]=1;
            }
        }
        else low[u]=min(low[u],dfn[To[i]]);
    }
    if(u==pre&&son>1) {//根割點 
         node[u]=1;
         NUll=false;
    }
}

void _cout(int n)
{
    int fir=0;
    if(NUll) printf("Null");
    else 
    for(int i=1;i<=n;i++){
        if(node[i]){
            printf("%d ",i);
        }
    }
    printf("\n");
    sort(s+1,s+cut_num+1,cmp);
    for(int i=1;i<=cut_num;i++)
        printf("%d %d\n",s[i].x,s[i].y);//當然無重邊，不然也得set判重 
}

int main()
{
    int n,m,i,j,u,v;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,1);//如果是森林，得for掃描一遍!dfn 
    _cout(n);
    return 0;
}      

It is your time to fight！