深度优先生成树及其应用

/*数据结构：邻接表存储图
程序说明：为简单起见，设节点的类型为整型，设visited[],num[].low[],parent[]为全局变量，
为求得先序编号num[]，设置全局变量counter并初始化为1。为便于单独处理根节点设置root变量。
*/#include <cstdio>#include <vector>#include <algorithm>

using namespacestd;

const int MAX_N = 100;
vector<int>graph[MAX_N];
vector<int>artPoint;
intnum[MAX_N], low[MAX_N], parent[MAX_N];
int counter = 1;
introot;
boolvisited[MAX_N];

void Init();           //初始化图
void FindArt(int v);   //找到第二类割点
void PrintArtPoint();  //打印所有割点(第一类割点在此单独处理)

intmain()
{
    Init();
    FindArt(root);
    PrintArtPoint();
    return 0;
}

voidPrintArtPoint()
{
    int rootChild = 0;  //根节点的孩子个数
    for (int i = 0; i < graph[root].size(); i++) //计算根节点的孩子个数
{
        if (parent[graph[root][i]] ==root)
            rootChild++;
    }
    if (rootChild > 1)            //根节点孩子个数大于1则为割点
artPoint.push_back(root);
    for (int i = 0; i < artPoint.size(); i++)
        printf("%d
", artPoint[i]);
}

voidInit()
{
    inta, b;
    root = 1;
    while (scanf("%d%d", &a, &b) !=EOF)
    {
        graph[a].push_back(b);
        graph[b].push_back(a);
        visited[a] = false;
        visited[b] = false;
    }
}
void FindArt(intv)
{
    visited[v] = true;
    low[v] = num[v] = counter++;          //情况(1)
    for (int i = 0; i < graph[v].size(); i++)
    {
        int w =graph[v][i];
        if (!visited[w])           //树边
{
            parent[w] =v;
            FindArt(w);
            if (low[w] >= num[v] && v !=root)
                artPoint.push_back(v);
            low[v] = min(low[v], low[w]);  //情况(3)
}
        else if (parent[v] != w)           //回退边
{
            low[v] = min(low[v], num[w]);  //情况(2)
}
    }
}

/*数据结构；邻接表
程序说明：1. 每对Gr进行一次DFS，生成一个强连通分量，topSort++,
          所以topSort相同的顶点即在同一个强连通分量中。
        2. 为便于得到最大编号对应的顶点，设置node[]，其下标为后序编号，值为对应顶点
*/#include <cstdio>#include <vector>#include <cstring>#include <cstdlib>
using namespacestd;
const int MAX_N = 100;
vector<int> G[MAX_N];  //原图
vector<int> Gr[MAX_N]; //反转后的图
vector<int> topSort[MAX_N];    //下标为所属强分支的拓扑序
int counter = 0;       //用于编号
int node[MAX_N];       //后序遍历标号，下标为编号
boolvisited[MAX_N];
int vNum;              //图的顶点数
void DFS(intv);
void RDFS(int v, int k);  //参数k为v所在的强连通分量的拓扑序
int SCC();                //返回强连通分量的个数
void Init();              //初始化图G和Gr
intmain()
{
    Init();
    int sccNum =SCC();
    printf("%d
", sccNum);
    for (int i = 0; i < sccNum; i++)
    {
        intj;
        printf("{");
        for (j = 0; j < topSort[i].size()-1; j++)
            printf("%d, ", topSort[i][j]);
        printf("%d}
", topSort[i][j]);
    }
    return 0;
}
voidInit()
{
    scanf("%d", &vNum);
    intu, v;
    while (scanf("%d%d", &u, &v) !=EOF)
    {
        G[u].push_back(v);
        Gr[v].push_back(u);   //反向
}
}
void DFS(intv)
{
    visited[v] = true;
    for (int i = 0; i < G[v].size(); i++)
    {
        if (!visited[G[v][i]])
            DFS(G[v][i]);
    }
    node[counter++] = v;     //后序遍历
}
void RDFS(int v, intk)
{
    visited[v] = true;
    topSort[k].push_back(v);         //将属于同一强连通分量放一起
    for (int i = 0; i < Gr[v].size(); i++)
    {
        if (!visited[Gr[v][i]])
            RDFS(Gr[v][i], k);
    }
}
intSCC()
{
    memset(visited, false, sizeof(visited));
    for (int v = 1; v <= vNum; v++)
    {
        if (!visited[v])
            DFS(v);
    }
    memset(visited, false, sizeof(visited));
    int k = 0;           //初始化第一个强连通分量的拓扑序为1
    for (int i = --counter; i >= 0; i--) //从编号最大开始
{
        if (!visited[node[i]])
            RDFS(node[i], k++);
    }
    returnk;
}

Tarjan(u)
{
    num[u]=low[u] = counter              //情况(1)
    Stack.push(u)                        //将节点u压入栈中
    for each (u, v) in E                  //枚举每一条边
        if (v is not visted)              //如果节点v未被访问过
            Tarjan(v)                    //继续向下找
            low[u] = min(low[u], low[v]) //情况(3)
        else if (v in Stack)             //如果节点v还在栈内
            Low[u] = min(low[u], num[v]) //情况(2)
    if (num[u] == low[u])                //如果节点u是强连通分量的根
repeat
            v = Stack.pop                //将v退栈，为该强连通分量中一个顶点
print v
        until (u==v)
}