思路描述
本蒟蒻看见标签写着Floyd、传递闭包,再看见各位大神写的Dfs、贪心…这些算法我这个菜鸡都不会啊…不过看到这道题就让我想起来以前写过的拓扑排序的题,所以在WA了几次之后成功AC 开心>W<
仔细阅读题意之后可以发现这道题非常的友好,首先数据范围较小,其次已经说明了只含有n-1条边,并且使得从每个加工站出发都可以到达所有其他加工站,这就代表着图中绝对不含有环(简单易证,因为如果带有环,则一定会有一个顶点与其他任何顶点都不想连,因为边数是有限的,那么就不符合题意了)。那么我们就可以通过判断每个点的入度和出度进行拓扑排序来找到是否存在某个顶点符合题意。
根据拓扑排序的思想,我们每次都删除一个入度为0的点,并且检查剩余的所有点,将所有与该被删除的点连通的点入度减一。不难想出,一段道路的尽头的点的出度一定为0(因为这个点不会再能走到别的点了),那么我们就先记录下这个点的序号。如果我们多次找到了这种出度为0的点,那么说明一定不符合题意(可以自己画图看一下,如果存在两个这种点,那么这两个点之间一定无法到达)。
上代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int x;
int indegree;
int outdegree;
} m[105];
int r[105][105]; //代表是否连通
int main()
{
int n;cin>>n;
for (int i=1;i<=n;i++) m[i].x=i; //预处理一下结点的标号
for (int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
m[a].outdegree++;
m[b].indegree++;
r[a][b]=1;
}
queue<node> q;
for (int i=1;i<=n;i++)
{
if (m[i].indegree==0) q.push(m[i]);
}
int num=0,ans;
while(!q.empty())
{
node t=q.front();q.pop();
for (int i=1;i<=n;i++)
{
if (r[t.x][i]==0) continue;
m[i].indegree--;
if (m[i].indegree==0)
{
if (m[i].outdegree==0) //代表是一段道路的尽头
{
ans=m[i].x;num++;
}
else q.push(m[i]);
}
}
}
if (num>=2) cout<<-1;
else cout<<ans;
return 0;
}
dfs应该也行 搜到头了就记录一下 如果搜到了两次及以上尽头就是-1
求关注
不不不
不不不