本文共 2754 字，大约阅读时间需要 9 分钟。
先上代码
//好了接下来是我自己写的...难得能自己这么快乐的打代码的时光珍惜吧= -//一种又要抄高数作业的节奏....所以我之前是在干嘛?//所以我要是直接不写高数作业不就完全ojbk了#include//dfs(1,0) 之后继续, 爸爸是0,1里面只有一个2,访问2 用爸爸来限制吧.. 如果你是又访问到一次,那你就是有环 并且,一个是x,一个是i啊 这个x是初始的,i是你读入的g[x] i里面那一堆.,, = = 因为,还是搜索吗,所以dfs的时候,你最开始push进来的这几条边,我都要跑他一炮 炮的时候,每次遇到不合格的... 不合格的就是(之前已经用过了一次!) 或者你没用到,但是你跑到别人家的bfs里面 去! (因为循环调用的嘛,深度优先,所以一条路走到黑了) 跑到人家的dfs里面去,直到逼得他最后一步都无路可走(并且还没有退出)就表明,一路上的dfs都是安全通过的.... ****这和bfs其实一样的吗...bfs就是啥都不管,有啥先都扔进去,那bfs就是一条路走到黑,不停的在递归递归递归递归 bfs就是你不满足就滚,满足就继续跟我递归 直到不能递归了,返回一个很安全的路径,那就是这个题里面return 1(zj说写错了,反正就是无环) // 可以说是分块的啊.... 其实循环调用的话一直在里面dfs也还好,毕竟是在相互调用,里面完了就出结果了 如果还是那种真的分的很开的,那就分开调用嘛. g[x],从(1,0)跑没了,安全,不要怕,我们.... 不对....要怕了,从(1,0)跑完了,就没了啊... 所以吧....所以,如果是判断什么连通快的,就不能用了, 这个代码适合的是一条路走到黑的类型,因为它是一条通路呀,通路里面如果(在去除了爸爸之后)有另外的循环出现,那就是有环图... ***另,对于 3 4 4 3 这种直接自己和自己相连 的似乎就已经没法判断了,因为你是从爸爸那里来到的,所以上述代码是(去除了直接34 43这种之后的,大环的有无爸爸情况的代码) *** 3 4 4 3 这种呢,我们直接用vector来判断就好了 加的时候 v.push_back(u); u.push_back(v); 那么加的时候直接加了两次啊... 4 4 sort一下,如果有重复的就输出= - 需要先这么预处理一下,还是挺快的吧... ***还有一个问题就是,这个是用.. [邻接表]啊,也就是 vector<T> g[mn]来实现的(命名规则而已...其实也就是m吧) g[1]她们一开始数据块范围都挺小的 然后你把它打压进去 g[2]有几个他能访问到的点 这个vector数据范围就多大 ***其他的一些 n是点数 m是边数(边数是输入的时候用的,相当于输入了2m个嘛) n有用啊,,,,大概g[mn]里面这么多,下一次再使用需要清空的时候就clear一下,over ***怎么写了这么多= - ***大概和dfs一样需要【提炼一下步骤以免忘了】 【抽象模板的话就是】 对于这种是否是有向图 的问题。。。。 1.读入边（两个点），分别塞入向量（邻接表）2次 2.bfs：bfs的话！ （1）首先，需要记忆一下【爸爸】 （2）进来之后标记成1（已经访问过） （3）对于搞到x这个数组里面的所有k都访问一遍 （就是k=g[x][i]） (4)k的话特别注意一下排除等于爸爸的问题(误判(k!=fa)) (5)如果你vist或者是bfs下一个穷追不舍等于1了都会推出 (6)循环一样的往下跑就好了 3.如果返回1，就是NO 【再总结一下的话就是】 /1肚入边/2小范围:访问标记/3搞进去的数组清洗干净 /4小范围:搞进去的数组/5 搞进去的数组不等于爸爸,没访问过,或者道上的人 也就是两个小嵌套啦#include using namespace std; const int mn = 10005; //*****要加constint vis[mn];//0就是没访问过就是NO 1就是访问过就是YES int u; int v;//u和v定义到里面还是有问题.....vector g[mn];int bfs(int x,int fa){ vis[x] = 1; for (int i = 0; i < g[x].size(); i++) { int k = g[x][i]; ******以及!!!vector这个数组也是有点毛病,是g[x][i],前面是对应的第几个坐标,后面是这个//后面是这个坐标里面的第几个数据,你加了几个啦...什么的 ********** *****非常重要的一点啊!那就是爸爸这个你既然传进来想用了 就要排除这个特殊情况,因为它算作是多数了,不算的! if(k != fa) { if (vis[k] || bfs(k, x) == 1) return 1; } //回去的时候就会不断的叠加..叠加,....知道跌回最后一个0输出了.over!是不是非常完美! //**这里是或者...活着就是只要有一个满足了这个玩意儿 //要么被访问过 或者你一条路走到黑 你道儿上的人也犯过事儿 那你就滚了 } //here we know if it returuns 0 is no //and 1 is yes return 0;//if there is nothing //平安运行就是0啊= -}int main(){ int m, n; cin >> n >> m; for (int i = 1; i <= m; i++)//(等于号,小错误不要翻 {cin>>u>>v; g[u].push_back(v); g[v].push_back(u); //初始化工作是把两个都加进去对吧= } if (bfs(1, 0) == 1)cout << "NO"; else cout << "YES";//0 is无 //1就是又换= - return 0;}
最后感谢大家哦(鞠躬)
zj的原代码= -我似乎写错了
#includeusing namespace std;/*dfs判断无向图是否有环 */ const int mn=1e5+5;int n,m;//the number of pointvector g[mn]; bool vis[mn];int dfs(int x,int fa){ vis[x]=1; for(int i=0;i
转载地址：http://zquti.baihongyu.com/