福建建筑人才网官方网站,网站域龄查询,wordpress在线制作网页,重庆网站建设帝维科技题目大意#xff1a;给定一张边权为1的无向图#xff0c;问是否存在长度为奇数的环和长度为偶数的环。(n105,m3*105) 调都调不好的的代码 容易想到的是#xff0c;从一个点x开始DFS#xff0c;如果两次访问到一个点#xff0c;这两条路径就会构成一个环 根据两次到…题目大意给定一张边权为1的无向图问是否存在长度为奇数的环和长度为偶数的环。(n105,m3*105) 调都调不好的的代码 容易想到的是从一个点x开始DFS如果两次访问到一个点这两条路径就会构成一个环 根据两次到达的时候该点与x的距离就能算出环的的长度 两个如果一个点属于两个奇环图中就存在至少一个偶环 代码 1 #include iostream2 #include cstdio3 #include cstring4 #include vector5 #define M 1000106 #pragma comment(linker, /STACK:102400000,102400000)7 using namespace std;8 vectorint vec[M];9 int deep[M],vis[M];
10 int ans[2];
11 int eve[M];
12 void dfs(int x,int fa)
13 {
14 vis[x]1;
15 int szvec[x].size();
16 for(int i0;isz;i)
17 {
18 int tovec[x][i];
19 if(tofa) continue;
20 if(vis[to])
21 {
22 if(deep[x]deep[to])
23 {
24 int len(deep[x]-deep[to]1)1;
25 ans[len];
26 if(len%21)
27 {
28 eve[x];
29 if(eve[to]) ans[0];
30 }
31 }
32 continue;
33 }
34 deep[to]deep[x]1;
35 dfs(to,x);
36 }
37 }
38
39 int main()
40 {
41 int T;
42 scanf(%d,T);
43 while(T--)
44 {
45 int n,m;
46 scanf(%d%d,n,m);
47 ans[0]ans[1]0;
48 memset(vis,0,sizeof(vis));
49 memset(eve,0,sizeof(eve));
50 memset(deep,0,sizeof(deep));
51 for(int i0;in;i) vec[i].clear();
52 for(int i0;im;i)
53 {
54 int u,v;
55 scanf(%d%d,u,v);
56 vec[u].push_back(v);
57 vec[v].push_back(u);
58 }
59 for(int i1;in;i)
60 if(!vis[i])
61 dfs(i,0);
62 if(ans[1]) puts(YES);
63 else puts(NO);
64 if(ans[0]) puts(YES);
65 else puts(NO);
66 }
67 return 0;
68 } 转载于:https://www.cnblogs.com/Slrslr/p/9527728.html
