P1700
HasNoName
·
·
题解
问题
在一张 N 个点有向图中，求编号最小的，所有点都能到的点。
没有所有点都能到的点输出 -1。
### 方法
用一个数组统计每个点能被走到的数量。
对每个点进行搜索，把能到的点的能被走到的数量增加 $1$。
如果一个点能被走到的数量是 $N-1$ 则所有的点都能到。
### 代码
```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int N=105;
int w[N];//每个点能被走到的数量
bool vis[N];
struct T
{
int to,ne;
}e[N];
int he[N],idx;
void add(int x,int y)//建图
{
e[++idx].ne=he[x];
e[idx].to=y;
he[x]=idx;
}
void dfs(int x)//遍历
{
vis[x]=1;//每个点只走一次
for(int i=he[x];i;i=e[i].ne)//遍历每个临点
{
int y=e[i].to;
if(!vis[y])//没被遍历过
{
w[y]++;
dfs(y);
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,x,y;
cin>>n;
for(int i=1;i<n;i++)
{
cin>>x>>y;
add(x,y);
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));//清空数组
dfs(i);
}
for(int i=1;i<=n;i++)
{
if(w[i]==n-1)
{
cout<<i<<'\n';
return 0;
}
}
cout<<"-1\n";//无解
return 0;
}
```
[记录](https://www.luogu.com.cn/record/143258851)。