HDU - 4324 Triangle LOVE--补题 拓扑排序

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

26

题意:有n个人,每个人之间是单向喜欢的关系,问是否存在a喜欢b,b喜欢c,c喜欢a的三角恋关系。

条件:1 每个人之间都有一个单向的关系

            2 三角恋就是成三元环

思路:因为每个人之间都有一个单向的关系,所以三角恋就是成环,成环一定会有三元环。采用拓扑排序来判断是否成环。

扩展:拓扑排序,就是有向图中每次把入度0的点放入队列中,然后该点指向的点入度减一,然后再找下一个入度为0的放入队列,然后出队列再重复。如果最后拓扑序列里面的总数小于n,就说明有环。

代码:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
char mp[2005][2005];//关系图
int num[2005];//入度记录
int topusort(int n)
{queueque;for(int i=0;i

总结:1 当时想到拓扑序列,可是不够熟练,然后没有读出题目中每个人之间都有一个单向的关系的条件,所以一直卡在怎么找三元环的中。