TOJ::179 / 謠言問題

http://2014.sprout.csie.org/oj/pro/179/
2009 TOI 研習營初選，割點的進化問題。



題目問怎麼樣拔掉一個點可以使從一個根DFS走訪的點數最少。

其實就是找割點，重點是如何得知哪個割點割出來最小。

我們可以知道，如果一個點是割點，拔掉他，會讓其中一顆子樹或是多顆子樹斷掉，那我們先寫一個DFS可以統計走訪個數，順便找割點。

如果某個點的某個子樹最高只能走到這個點或以下，那代表這個點是割點，也間接代表拔掉該點會拔掉該子樹，所以把DFS這個子樹的點的總和加到一個陣列裡，代表拔掉這個點會拔掉多少子節點，要注意可能同時拔掉好多顆子樹，所以判完不能break要跑完。

最後，只要 for i in 1...n，如果 i 是割點，用點的總數(剛剛DFS統計過，因為圖有可能不連通，不能直接用 n)減掉 i 點子樹的節點數+1( i 也要算進去)去更新最小值就好。

因為根節點是不是割點並不會影響題目(題目要求不能拔根)，所以跟的特判就省了。

#include <cstdlib>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 30001
#define LL long long
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
int low[N],dfs[N],wed[N],dfst,root;
bool IF[N];
vector<int> D[N];
int DFS(int now,int no){
    int sum=wed[now]=1;
    low[now]=dfs[now]=dfst++;
    F(D[now].size()){
        if(wed[D[now][i]]==0){
            int tmp=DFS(D[now][i],now);
            sum+=tmp;
            if(dfs[now]<=low[D[now][i]]&&now!=root){
                IF[now]=true;
                wed[now]+=tmp;
            }
        }
        if(D[now][i]!=no)low[now]=min(low[now],low[D[now][i]]);
    }
    return sum;
}
int main(int argc,char *argv[])
{
    ios_base::sync_with_stdio(false);
    int n,m,a,b,mi=2147483647;
    cin>>n>>m;
    F(m){
        cin>>a>>b;
        D[a].push_back(b);
        D[b].push_back(a);
    }
    cin>>root;
    int sum=DFS(root,root);
    b=0;
    F(n)if(IF[i+1]){
        if(sum-wed[i+1]+1<mi){
            mi=sum-wed[i+1]+1;
            b=i+1;
        }
    }
    if(mi==2147483647)cout<<0<<endl;
    else cout<<b<<' '<<mi<<endl;
    //F(n)cout<<wed[i+1]<<' ';cout<<endl;
    system("pause");
    return 0;
}