Algorithm --> 树中求顶点A和B共同祖先

树中求顶点A和B共同祖先

题目：

　　给定一颗树，以及两个顶点A和B，求最近的共同祖先，和包含的子顶点个数？

比如：给定如下图的树，以及顶点13和8，则共同祖先为3，以3为root的子顶点共有8个

条件：

1、顶点的标号从1到V，根节点是1

2、给定顶点A和B， 求最近的祖先

代码1：

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

#define _DEBUG 0
#define MAX 10001

int T;
int Answer, nCount;
int N, E, src, des;
int tree[MAX][MAX];
int count[MAX];
int parent[MAX];
bool visited[MAX];

void InitData()
{
    for(int i = 0 ; i < MAX; i++) {
        for(int j = 0 ; j < MAX; j++) {
            tree[i][j] = 0;
        } 
        visited[i] = false;
        count[i] = 0;
        parent[i] = 0;
    }
}

int _Count(int node)
{
    int cnt = 1;
    
    for(int i = 0; i < count[node]; i++) {
        cnt += _Count(tree[node][i]);
    }
    
    return cnt;
}

int main()
{
   // freopen("input_commonancestor.txt", "r", stdin);
    
    cin >> T;
    for(int tc = 0; tc < T; tc++) {

        Answer = 1;
        nCount = 0;
        
        InitData();
        
        cin >> N >> E >> src >> des;

        int start, end;
        for(int i = 1; i <= E; i++) {
            cin >> start >> end;
            tree[start][count[start]++] = end;
            parent[end] = start;
        }

        int node = src; 
        do {    //找出src的所有父节点，并置为true
            visited[node] = true;    
            node = parent[node];
        }while(node);

        node = des;
        do {   //从des点出发找父节点，每个父节点判断是否为true
            if(visited[node] == true) break;
            node = parent[node];
        }while(node);

        if(node > 0)
            nCount = _Count(node);  //找出以node为顶点的树的结点个数

        cout << "case# " << tc << " : " << node << " " << nCount << endl;
    }
}

代码2：

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

#define _DEBUG 0
#define MAX 10001

int T;
int Answer, Count;
int N, E, src, des;
int graph[MAX][MAX];
int hash[MAX];
int visited[MAX];

void InitData()
{
    for(int i = 0 ; i < MAX; i++) {
        for(int j = 0 ; j < MAX; j++) {
            graph[i][j] = 0;
        }
        hash[i] = 0;
        visited[i] = 0;
    }
}

void FindParent(int v)
{   
    hash[v] = 1;
    
    if(v == 1)
        return;

    for(int i = 1; i <= N; i++) {
        if(hash[i] == 0 && graph[i][v] == 1)
        {
            hash[i] = 1;
            FindParent(i);
        }
    }
}

void FindAncestor(int d)
{
    if(hash[d] == 1) {
        Answer = d;
        return;
    }

    if(d == 1) {
        return;
    }

    for(int i = 1; i <= N; i++) {
        if(graph[i][d] == 1) {
            FindAncestor(i);
        }
    }
}

int _Count()  //BFS计算顶点个数
{
    int res = 0;
    queue<int> q;
    
    visited[Answer] = 1;
    
    q.push(Answer);

    while(!q.empty()) {
        int top = q.front();
        q.pop();
        
        res++;

        for(int i = 1; i <= N; i++) {
            if(visited[i] == 0 && graph[top][i] == 1) {
                visited[i] = 1;
                q.push(i);
            }
        } 
    }
    return res;
}

int main()
{
    freopen("input_commonancestor.txt", "r", stdin);
    
    cin >> T;
    for(int tc = 0; tc < T; tc++) {

        Answer = 1;
        Count = 0;
        
        InitData();
        
        cin >> N >> E >> src >> des;

        int a, b;
        for(int i = 1; i <= E; i++) {
            cin >> a >> b;
            graph[a][b] = 1;
        }

        FindParent(src);

#if _DEBUG
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                cout << graph[i][j] << " ";
            }
            cout << endl;
        }
        for(int i = 1; i <= N; i++) {
            cout << "hash[" << i << "] = " << hash[i] << endl;
        }
#endif

        FindAncestor(des);

        if(Answer == 1)
            Count = N;
        else
            Count = _Count();

        cout << "case# " << tc << " : " << Answer << " " << Count << endl;
    }
}

输入文件：

5
13 12 8 13
1 2 1 3 2 4 3 5 3 6 4 7 7 12 5 9 5 8 6 11 6 10 11 13
10 9 2 10
1 2 1 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
50 49 24 31
31 7 2 17 27 32 14 30 1 21 45 26 44 27 39 11 26 3 48 6 3 44 2 49 42 13 48 8 23 33 11 10 8 42 41 31 17 4 8 22 25 23 21 41 28 25 13 16 46 2 31 35 42 19 32 18 27 50 45 15 28 20 46 28 44 40 40 5 15 48 9 34 1 46 17 29 35 36 21 45 14 37 23 14 6 39 11 9 19 24 26 47 16 38 40 12 47 43
100 99 24 7
38 9 68 100 81 10 1 62 25 24 15 92 73 75 16 87 84 86 59 72 94 67 37 70 69 46 88 35 62 90 28 15 5 61 43 98 10 89 21 88 76 69 87 47 80 23 49 31 63 19 61 99 54 78 18 36 79 33 11 30 77 40 47 26 73 95 22 91 15 38 50 44 62 39 100 13 93 97 89 53 39 37 14 80 5 54 49 94 48 58 55 12 40 82 51 3 87 7 45 4 82 14 31 32 30 64 93 42 10 48 40 25 21 77 37 71 90 50 35 76 20 34 96 59 25 85 77 81 58 56 57 79 76 11 81 84 14 57 60 16 88 8 96 21 43 63 83 17 57 93 94 18 69 28 28 5 42 2 98 55 70 74 80 66 91 73 61 68 13 41 35 51 1 96 19 29 79 43 60 83 68 27 51 65 42 52 11 45 70 60 90 22 39 49 52 20 17 6
200 199 45 145
181 101 35 149 49 95 134 16 69 35 127 59 28 92 168 51 81 131 2 20 61 161 40 113 71 63 67 42 21 198 193 108 17 13 194 103 76 11 101 73 39 30 186 69 91 96 174 133 39 38 136 74 142 187 164 178 77 200 128 141 110 118 14 56 1 194 60 166 148 173 51 167 124 39 180 181 47 128 18 22 52 81 72 90 26 123 53 66 78 146 155 156 79 158 171 12 63 134 192 57 147 195 47 65 99 62 65 169 77 154 165 130 57 175 188 115 190 93 10 165 59 4 98 139 194 86 197 114 83 148 175 160 140 99 117 193 165 25 167 67 177 183 123 188 13 23 186 60 166 54 12 176 163 168 188 32 195 41 107 104 42 75 85 126 112 132 84 135 7 129 65 64 8 2 119 46 44 10 50 152 184 153 53 116 17 172 92 144 58 150 172 3 162 184 50 182 97 109 49 87 190 36 41 34 80 179 103 106 84 145 76 21 71 94 23 138 58 140 166 78 28 88 99 33 73 5 117 112 167 177 136 40 192 28 109 27 152 31 174 117 172 98 38 84 63 43 156 15 6 79 54 47 171 136 73 6 124 17 94 61 197 157 45 191 45 29 103 58 110 9 147 155 97 124 140 171 134 125 81 159 92 142 15 127 36 8 168 119 11 199 115 44 91 111 105 89 26 180 22 71 176 102 42 77 106 80 106 164 29 137 60 37 32 7 170 105 54 121 38 52 120 122 152 19 114 174 22 170 170 76 150 197 87 82 115 45 86 147 162 68 19 48 155 185 180 70 3 151 163 186 13 107 86 143 85 120 3 83 69 192 123 91 18 26 118 196 143 189 51 18 67 49 41 190 1 163 79 14 111 72 193 55 27 162 150 50 5 53 109 85 78 24 119 97 195 100 133 110
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jeakeven/p/4798433.html