(UVA) 10765 - Doves and bombs

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1706

割點的強化XD

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 10004;

int low[MAX_N];
int depth[MAX_N];
vector<int> edg[MAX_N];
bool visit[MAX_N];
int cut_vertex[MAX_N];
int son[MAX_N];
pii ans[MAX_N];

void dfs(int id,int cur_depth,int parent) {
    low[id]=cur_depth;
    visit[id]=true;
    depth[id]=cur_depth;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp] ==true) {
            if (low[id] > depth[tmp]) {
                low[id] = depth[tmp];
            }
        }
        else {
            son[id]++;
            dfs(tmp,cur_depth+1,id);
            if (low[tmp] < low[id]) low[id]=low[tmp];
            else if (low[tmp] >= cur_depth && id!=parent){
                cut_vertex[id]++;
            }
        }
    }
    if (id==parent) cut_vertex[id]=son[id];
}

int main () {
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        if (!n && !m) break;
        for (int x=0;n>x;x++) {
            edg[x].clear();
            visit[x]=false;
            cut_vertex[x] = 1;
            son[x]=0;
        }
        int i,j;
        while (scanf("%d %d",&i,&j)) {
            if (i==-1&&j==-1) break;
            edg[i].push_back(j);
            edg[j].push_back(i);
        }
        dfs(0,1,0);
        for (int x=0;n>x;x++) {
            ans[x]=make_pair(cut_vertex[x],-x);
        }
        sort(ans,ans+n);
        for (int x=n-1;x>=n-m;x--) {
            printf("%d %d\n",-ans[x].second,ans[x].first);
        }
        puts("");
    }
}