UVA 10765 Doves and bombs 割点

最近好懒，堆了好多题没写题解。。

原题链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1706

题意：

给你一个图，问你每个点去掉后有多少个联通块

题解：

就Tarjan一下就好，很简单

代码：

#include<iostream>

#include<cstring>

#include<vector>

#include<queue>

#include<cstdio>

#include<string>

#include<algorithm>

#define MAX_N 11234

using namespace std;

int n,m;

vector<int> G[MAX_N];

int dfn[MAX_N],low[MAX_N],ind=;

bool vis[MAX_N];

struct node{

    public:

        int pos,val;

        void print(){

            cout<<pos-<<" "<<val<<endl;

        }

};

bool cmp(node a,node b){

    if(a.val==b.val)return a.pos<b.pos;

    return a.val>b.val;

}

node d[MAX_N];

void Tarjan(int u,int p){

    d[u].pos=u,d[u].val=;

    dfn[u]=low[u]=++ind;

    vis[u]=;

    int child=;

    for(int i=;i<G[u].size();i++){

        int v=G[u][i];

        if(v==p)continue;

        if(!vis[v]){

            child++;

            Tarjan(v,u);

            low[u]=min(low[v],low[u]);

            if(low[v]>=dfn[u]&&p!=)d[u].val++;

        }

        else low[u]=min(dfn[v],low[u]);

    }

    if(p==&&child>)d[u].val=child;

}

void init(){

    memset(vis,,sizeof(vis));

    memset(dfn,,sizeof(dfn));

    memset(low,,sizeof(low));

    ind=;

    for(int i=;i<=n;i++)G[i].clear();

}

int main(){

    cin.sync_with_stdio(false);

    while(true){

        cin>>n>>m;

        if(n==&&m==)break;

        init();

        while(true){

            int u,v;

            cin>>u>>v;

            if(u==-)break;

            u++;v++;

            G[u].push_back(v);

            G[v].push_back(u);

        }

        Tarjan(,);

        sort(d+,d++n,cmp);

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

            d[i].print();

        cout<<endl;

    }

    return ;

}