标准的求割顶的问题,用tarjan算法,参见www.nocow.cn割点词条
/*
* poj1144 AC
* 求无向图割顶
* tarjan算法,好好背一背!
* */
#include<memory.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct NODE{
int v,next;
}edge[20020];
long tot,head[105];
int n,ans,dfn[105],low[105],sons,ind;
int tarjan(int x)
{
int i;
bool mark = false;
dfn[x] = low[x] = ++ind;
i = head[x];
while(i)
{
if(!dfn[edge[i].v])
{
if(x==1) sons++;
......
阅读全文