HDU 4587——TWO NODES(列挙+割頂)

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=4587
問題の意味は簡単で、1つのN個の点の無方向図を与えて、その中で1対のノードを見つけて、それを削除して残りのノードからなる連通ブロックを最も多くして、最も多くの連通ブロックを出力します.
最初は二つの結点を同時に列挙する方向に考えて、割頂や橋を探したが、例も破れなかった.
その後、1つの点を削除するだけで問題が多くなることがわかりました.ある点を削除することを考えて、より多くの連通ブロックを生成するには、この点は必ずトップになります.次に、この点を削除した連通ブロックの数を見てみましょう.私のやり方は、この点に接続されたエッジとブリッジの数を統計することです.もし両者が等しいならば、連通ブロック数はブリッジの数を増やして1を減らします.そうしないと、ブリッジの数を増やします.
だから最終的には、最初の点を削除してtarjanを走って、ここで最初の点をマークして、後ろを走っている間にアクセスしないでください.そしてこの場合のカットトップを列挙し、最大値を取ればよい.

#include
#include
#include
#include
using namespace std;
#define N 5000
#define pb push_back
struct Edge{
    int id, to;
};
vector V[N];
int con[N], low[N], pre[N], bridge[N], dfs_clock, ans, cnt;
bool vis[N], ban[N], cut[N];
void dfs(int x, int fa){
    low[x] = pre[x] = ++dfs_clock;
    int child=0;
    for(int i=0; ipre[x]){
                bridge[x]++;
                bridge[j]++;
            }
            low[x] = min(low[x], low[j]);
            if(low[j]>=pre[x]){
                cut[x] = 1;
            }
        }
        else{
            low[x] = min(low[x], pre[j]);
        }
    }
    if(fa<0 && child==1)    cut[x]=0;
}
int main(){
    int n, m, x, y;
    while(~scanf("%d %d", &n, &m)){
        for(int i=0; i