https://codeforces.com/group/5yyKg9gx7m/contest/269908/problem/F
题目描述：
有n个点，编号依次为1,2....n。同时输入n-1对a,b。表示可以从a处到达b处。问是否存在一个编号最小的点i，使得从任意一个点出发，最终都能到达点i。不存在输出-1。
分析：
单向图。先用邻接矩阵存起来。可以到达的记为true。然后对于每一个点，用bfs把能间接到达的点也标记为true。不过需要剪枝一下，比如如果点1已经能到达2了，而且1也可以通过3间接到达2。这时再通过3到2就没意义了。这时就不需要再次对2进行bfs。
代码：
#include <stdio.h> #include <cstring> #include <algorithm> #include <queue> #include <cmath> #include <iostream> using namespace std; bool map[105][105]; int main() { int n; cin>>n; for(int i=0;i<n-1;i++) { int a,b; scanf("%d %d",&a,&b); map[a][b]=true; } queue<int> q; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) continue; if(map[i][j]) { q.push(j); } } while(!q.empty()) { int w=q.front(); q.pop(); map[i][w]=true; for(int k=1;k<=n;k++) { if(w==k) continue; if(map[w][k]&&!map[i][k]) { q.push(k); } } } } bool is; bool isp=false; for(int i=1;i<=n;i++) { is=true; for(int j=1;j<=n;j++) { if(i==j) continue; if(!map[j][i]) { is=false; break; } } if(is) { printf("%d\n",i); isp=true; break; } } if(!isp) printf("-1\n"); return 0; }
原文：https://www.cnblogs.com/studyshare777/p/12354107.html