题意:
给你n-1条有向边,问有没有一个点是从所有点出发都可以到达的(连通的)。
先介绍一种不那么优秀也不那么简洁的方法。
方法一
思路:
floyd,对于i与k连通,k与j连通的情况就可以确认i与j连通,以此类推。
时间复杂度:O(n^3)
不太优秀,但是能过。
代码:
#include<iostream>
using namespace std;
int n,x,y;
bool a[105][105];
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
a[x][y]=true;//标记从x可以到y
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][k]&&a[k][j]) a[i][j]=true;
//如果i与k连通并且k与j连通,那么i与j连通
}
}
}
for(int i=1;i<=n;i++){
bool ch=true;
for(int j=1;j<=n;j++){
if(i!=j&&!a[j][i]){//如果某个点不能到i了,说明i点不符合题意
ch=false;
break;
}
}
if(ch){//如果符合题意就直接输出
printf("%d",i);
return 0;
}
}
printf("-1");
return 0;
}
不要离开,接下来介绍一种O(n)的解法,代码简洁得多。
方法二
思路:
要用这种方法,我们先看到题目中的一句话:农夫约翰的牛奶加工厂内有N个加工站,编号为1…N,以及 N−1条通道,每条连接某两个加工站。
关键是N-1条通道!那么要求出符合题意的点,这些有向边就一定会组成一棵树,而树根出度为0。
接下来就简单了,对于每个点,我们都记录一下它的出度,然后循环一次。因为这是一棵树,所以出度为0的点会有一个也仅有一个,否则一定不成立。大家可以参照下面的图或自己画图理解一下,出度为0的点的数量如果大于1就根本不能连接过去。符合的话记录一下然后输出就行了。
时间复杂度:优秀的O(n)
代码:
#include<iostream>
using namespace std;
int n,x,y,cnt,ans;
int c[105];//记录出度的数量
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
c[x]++;//x点多了一条出度(说实话这里改成bool数组也可以,还省空间)
}
for(int i=1;i<=n;i++){
if(!c[i]){//如果出度为0
cnt++;//记录一下,万一有多个就不能直接输出
ans=i;//如果只有这一个点出度为0的话ans的值就不会再变了
}
}
if(cnt==1) printf("%d",ans);//cnt的值为1时才合法
else printf("-1");
return 0;
}
看y总视频证明,牛哇大佬
优秀的O(n)佬
输麻了o(╥﹏╥)o,大佬们在说什么完全不懂
太秀了!
点名表扬
并查集好像也能做到O(n)
这样对于大多数人要简单一点,代码不长。当然也要看个人习惯和情况。
秀啊
这个题可以拓扑排序解呐
O(n) 大佬牛啊!
其实还有很多人也写了O(n)的算法,只是有更多人写了更高时间复杂度的代码AC后就没管了(我最开始就floyd过的)。不过嘛,代码能过就行,对于比较刁钻一点的数据再考虑切换思路优化吧。
说的好,学习了
我是想怎么让代码更简洁的时候才想到这个方法的,过了之后回头一看,别人都用这种方法写好题解了。
这证明我依然是个蒟蒻。
谦虚了,大佬👍
看LAC的题解,他那个就跟我的思路差不多
牛啊,自愧不如
不不不,思路其实没有你清晰,floyd那个做法你的代码比我的好理解多了。
主要是因为大佬您的O(n)算法让我不由自主的点了个
# 👍
想互粉一下,有问题找大佬您讨论下
OK,但寒假完了估计就不能天天上线了。
嗯
第二个方法有问题吧 如果1,2,3构成环,4指向5,答案应该是-1
5
1 2
2 3
3 1
4 5
题目保证了不会有这种情况。
“通道建设很昂贵,所以约翰选择使用了最小数量的通道,使得从每个加工站出发都可以到达所有其他加工站”这句话是以一个无向边的形式来表述的,n个点n-1条边就只能为一棵树,不会有环,只不过变成有向边时就不一定是棵树了。
哦哦看到了 没注意审题🤣
哈哈哈,互粉一个缓解气氛。
牛逼
大佬牛蛙
大佬牛哇
第二个方法有问题
?
请求指出错误。
等会,是我相错了😂
啊这这这。
那互粉一个呗。
(手动滑稽)
欧克