Tarjan--LCA算法的个人理解即模板

  1 #include<iostream>
  2 #include<vector>
  3 using namespace std;
  4 
  5 const int MAX=10001;
  6 int father[MAX];
  7 int rank[MAX];
  8 int indegree[MAX];//保存每个节点的入度
  9 int visit[MAX];
 10 vector<int> tree[MAX],Qes[MAX];
 11 int ancestor[MAX];
 12 
 13 
 14 void init(int n)
 15 {
 16     for(int i=1;i<=n;i++)
 17     {
 18 
 19         rank[i]=1;
 20         father[i]=i;
 21         indegree[i]=0;
 22         visit[i]=0;
 23         ancestor[i]=0;
 24         tree[i].clear();
 25         Qes[i].clear();
 26     }
 27 
 28 }
 29 
 30 int find(int n)
 31 {
 32     if(father[n]==n)
 33         return n;
 34     else
 35         father[n]=find(father[n]);
 36     return father[n];
 37 }//查找函数，并压缩路径
 38 
 39 int Union(int x,int y)
 40 {
 41     int a=find(x);
 42     int b=find(y);
 43     if(a==b)
 44         return 0;
 45     //相等的话,x向y合并
 46     else if(rank[a]<=rank[b])
 47     {
 48         father[a]=b;
 49         rank[b]+=rank[a];
 50     }
 51     else
 52     {
 53         father[b]=a;
 54         rank[a]+=rank[b];
 55     }
 56     return 1;
 57 
 58 }//合并函数，如果属于同一分支则返回0，成功合并返回1
 59 
 60 
 61 void LCA(int u)
 62 {
 63     ancestor[u]=u;
 64     int size = tree[u].size();
 65     for(int i=0;i<size;i++)
 66     {
 67         LCA(tree[u][i]);
 68         Union(u,tree[u][i]);
 69         ancestor[find(u)]=u;
 70     }
 71     visit[u]=1;
 72     size = Qes[u].size();
 73     for(int i=0;i<size;i++)
 74     {
 75         //如果已经访问了问题节点,就可以返回结果了.
 76         if(visit[Qes[u][i]]==1)
 77         {
 78             cout<<ancestor[find(Qes[u][i])]<<endl;
 79             return;
 80         }
 81     }
 82 }
 83 
 84 
 85 int main()
 86 {
 87     int cnt;
 88     int n;
 89     cin>>cnt;
 90     while(cnt--)
 91     {
 92         cin>>n;;
 93         init(n);
 94         int s,t;
 95         for(int i=1;i<n;i++)
 96         {
 97             cin>>s>>t;
 98             tree[s].push_back(t);
 99             indegree[t]++;
100         }
101         //这里可以输入多组询问
102         cin>>s>>t;
103         //相当于询问两次
104         Qes[s].push_back(t);
105         Qes[t].push_back(s);
106         for(int i=1;i<=n;i++)
107         {
108             //寻找根节点
109             if(indegree[i]==0)
110             {
111                 LCA(i);
112                 break;
113             }
114         }
115     }
116     return 0;
117 }