HDU - 3671 Boonie and Clyde (图的割点）

As two icons of the Great Depression, Bonnie and Clyde represent the ultimate criminal couple. Stories were written, headlines captured, and films were made about the two bank robbers known as Romeo and Juliet in a getaway car.

The new generation of Bonnie and Clyde is no longer cold-blooded killers with guns. Due to the boom of internet, they turn to online banks and scheme to hack the safety system. The safety system consists of a number of computers connected by bidirectional cables. Since time is limited, they decide that they will attack exactly two computers A and B in the network, and as a result, other computers won't be able to transmit messages via A and B . The attack is considered successful if there are at least two computers (other than A and B ) that disconnected after the attack.

As they want to minimize the risk of being captured, they need to find the easiest way to destroy the safety system. However, a brief study of the network indicates that there are many ways to achieve their objective; therefore they kidnapped the computer expert, you, to help with the calculation. To simplify the problem, you are only asked to tell them how many ways there are to destroy the safety system.

InputThere are multiple test cases in the input file. Each test case starts with two integers N (3<=N<=1000) and M (0<=M<=10000) , followed by M lines describing the connections between the N computers. Each line contains two integers A , B (1<=A, B<=N) , which indicates that computer A and B are connected by a bidirectional cable.

There is a blank line between two successive test cases. A single line with N = 0 and M = 0 indicates the end of input file.OutputFor each test case, output one integer number representing the ways to destroy the safety system in the format as indicated in the sample output.Sample Input

Sample Output

Case 1: 2

Case 2: 11

题意：
删除两个点，使图不联通，求方案数．
思路：
枚举第一个点，用割点判断第二点就行了．
注意删除第一个点之后剩下联通块内部点的个数为１的情况．

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#define fuck(x) cerr<<#x<<" = "<<x<<endl;

#define debug(a, x) cerr<<#a<<"["<<x<<"] = "<<a[x]<<endl;

#define ls (t<<1)

#define rs ((t<<1)|1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = ;

const int maxm = ;

const int inf = 0x3f3f3f3f;

const ll Inf = ;

const int mod = ;

const double eps = 1e-;

const double pi = acos(-);

int Head[maxn],cnt;

struct edge{

    int Next,v;

}e[maxm];

void add_edge(int u,int v){

    e[cnt].Next=Head[u];

    e[cnt].v=v;

    Head[u]=cnt++;

}

int Index = ;

int dfn[maxn], low[maxn], root;

bool vis[maxn];

int exc,num;

void dfs(int cur, int father) {

    if(cur==exc){ return;}

    num++;

    int child = ;

    Index++;

    dfn[cur] = Index;

    low[cur] = Index;

    for (int k = Head[cur]; k != -; k = e[k].Next) {

        if(e[k].v==exc){ continue;}

        if (dfn[e[k].v] == ) {

            child++;

            dfs(e[k].v, cur);

            low[cur] = min(low[cur], low[e[k].v]);

            if (cur != root && low[e[k].v] >= dfn[cur]) {

                if(!vis[cur]){

                    vis[cur]=true;

                }

            }

            if (cur == root && child == ) {

                if(!vis[cur]){

                    vis[cur]=true;

                }

            }

        } else if (e[k].v != father) {

            low[cur] = min(low[cur], dfn[e[k].v]);

        }

    }

}

int main() {

//    ios::sync_with_stdio(false);

//    freopen("in.txt", "r", stdin);

    int n,m;

    int cases=;

    while (scanf("%d%d",&n,&m)!=EOF&&(n||m)){

        cases++;

        exc=cnt=Index=;

        memset(Head,-, sizeof(Head));

        memset(dfn,,sizeof(dfn));

        memset(vis,,sizeof(vis));

        for(int i=;i<=m;i++){

            int x,y;

            scanf("%d%d",&x,&y);

            add_edge(x,y);

            add_edge(y,x);

        }

        int ans=;

        for(int i=;i<=n;i++) {

            memset(dfn, , sizeof(dfn));

            memset(vis, , sizeof(vis));

            Index=;

            exc = i;

            int d1,d2;

            int tot = ;

            dfn[exc]=-;

            d1=d2=-;

            for(int j=;j<=n;j++){

                if(!dfn[j]&&j!=exc){

                    tot++;

                    root=j;

                    num=;

                    dfs(j,j);

                    if(d1==-)d1=num;

                    else d2=num;

                }

            }

            if(tot==){//如果删除的点不是割点，那么和它组合的一定是割点（删除之后）

                for(int j=;j<=n;j++){

                    ans+=vis[j];

                }

            }else if(tot==){//这个点是割点，而且把原图分为了两部分

                if(d1==d2&&d1==){

                    ans+=;

                }//如果两部分的点数都是１，那么对答案没有贡献

                else if(d1==||d2==){ans+=n-;}//有一个是１，就不能删除那个独苗

                else ans+=n-;//既然都不是１，那就可以随便删除

            }else{

                ans+=n-;//有三块，可以任意删除

            }

        }printf("Case %d: %d\n",cases,ans/);

    }

    return ;

}

巴特西

HDU - 3671 Boonie and Clyde (图的割点）

最新文章

热门文章