割顶.cpp

本人参加ACM竞赛使用的一些算法模板

/************************************************************
*
*   DFS求割顶(poj	1144	Network)
*
*************************************************************/


#include <algorithm>
using namespace std;

int const MAXN = 100;
int T, N, root;//T为时间戳，N为节点数，root为根节点
int graph[MAXN][MAXN], cnt[MAXN];//图，用矩阵式邻接表记录
int Anc[MAXN];//记录祖先节点
int D[MAXN], C[MAXN], A[MAXN];//辅助数组
bool cut[MAXN];//bool数组记录该点是不是割顶
void init()
{//注意初始化
    for(int  i = 0; i < N; i++)
        C[i] = cnt[i] = cut[i] = 0;
    T = 0;
    root = 0;//注意点从0还是从1标记
}
void DFS(int k, int father, int deep)
{//dfs求割顶, 初次调用的时候，取k=0(若点从0开始标记）作为当前点，father为-1，depp为0
    int i, tot;
    C[k] = 1;
    D[k] = deep;
    Anc[k] = deep, tot = 0;
    for(int j = 0; j < cnt[k]; j++)
    {
        i = graph[k][j];
        if(i != father && C[i] == 1)
		{
            Anc[k] = min(Anc[k], D[i]);
		}
        if(!C[i])
        {
            DFS(i, k, deep + 1);
            tot++;
            Anc[k] = min(Anc[k], Anc[i]);
            if( (k == root && tot > 1) || (k != root && Anc[i] >= D[k]) )
			{//当k为根节点且多于一个子或者k非根节点而k的最远祖先大于等于k的访问深度
               cut[k] = true;
			}
        }
    }
    C[k] = 2;
    A[i] = ++T;
}