2557783_ac_31ms_664k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 52 行

#include <stdio.h>
#include <vector>
using namespace std;
vector <int> tree[10001];
int n, mark;
int visited[10001];

void dfs(int v)
{
	int i;

	visited[v]++;
	if(visited[v]==2)
	{
		mark = 1;
		printf("%d\n",v+1);
		return ;
	}
	for(i = 0; i < tree[v].size(); i++)
	{
		if(mark)
			return ;
		dfs(tree[v][i]);
	}
}

int main()
{
	int i;
	int cas;
	int a, b;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d",&n);
		mark = 0;
		for(i = 0; i < n; i++)
			tree[i].clear();
		for(i = 1; i < n; i++)
		{
			scanf("%d%d",&a,&b);
			a--,b--;
			tree[b].push_back(a);
		}
		scanf("%d%d",&a,&b);
		a--,b--;
		memset(visited,0,sizeof(visited));
		dfs(a);dfs(b);
	}
	return 0;
}