Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Tarjan_LCA

Posted by Gaohf at 2017-09-15 21:06:35 on Problem 1330
```#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MaxN=10007;
vector <int> a[MaxN];
int f[MaxN],vis[MaxN],ans,n,t,x,y,isf[MaxN];
void tarjan(int);
int findroot(int);
int main()
{
scanf("%d",&t);
while(t--)
{
memset(f,-1,sizeof(f));
memset(vis,0,sizeof(vis));
memset(isf,0x3f,sizeof(isf));
for(int i=1;i<=n;i++)
{
a[i].clear();
}
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
isf[y]=0;
}
scanf("%d%d",&x,&y);
for(int i=1;i<=n;i++)
{
if(isf[i]){tarjan(i);break;}
}
printf("%d\n",ans);
}
return 0;
}
void tarjan(int x)
{
for(int i=0;i<a[x].size();i++)
{
tarjan(a[x][i]);
f[a[x][i]]=x;
}
vis[x]=1;
}
int findroot(int x)
{
return f[x]==-1 ? x : f[x]=findroot(f[x]);
}```

Followed by: