zstu.4191: 无向图找环(dfs树 + 邻接表）

4191: 无向图找环

Time Limit: 5 Sec Memory Limit: 128 MB Submit: 117 Solved: 34

Description

给你一副无向图，每条边有边权，保证图联通，现在让你判断这个图是否有异或值大于零的环存在。

Input

多组测试数据，每组先输入两个数n m，表示图的点跟边的数量。

然后是m行，每行三个数a b c。代表一条边的起点，终点，边权。

1 <= n<= 100000, 1 <= m <= 200000.

1 <= a <= n, 1 <= b <= n, a != b.

0 <= c <= 32767

Output

对于每组数据输出Yes或者 No。

Sample Input

Sample Output

No

HINT

Source

Wuyiqi

 1 #include<cstdio>
 2 #include<map>
 3 using namespace std;
 4 const int N = 100000 + 10 , M =  200000 + 10 ;
 5 struct edge
 6 {
 7     int u , v , nxt ;
 8     int w ;
 9 }e[M * 2];
10 int head[M * 2] , E = 0 ;
11 bool vis [N] ;
12 int sumxor[N] ;
13 int n , m ;
14 int u , v , w ;
15 bool flag ;
16 
17 void add (int u , int v , int w)
18 {
19     e[E].u = u , e[E].v = v , e[E].w = w , e[E].nxt = head[u] ;
20     head[u] = E ++ ;
21     e[E].u = v , e[E].v = u , e[E].w = w , e[E].nxt = head[v] ;
22     head[v] = E ++ ;
23 }
24 
25 void dfs (int u)
26 {
27     for (int i = head[u] ; i != -1 ; i = e[i].nxt) {
28         if (! vis[e[i].v]) {
29             vis[e[i].v] = 1 ;
30             sumxor[e[i].v] = sumxor[u] ^ e[i].w ;
31             dfs (e[i].v) ;
32         }
33         else {
34             if ( (sumxor[e[i].v] ^ sumxor[u] ^ e[i].w) ) {
35                 flag = 1 ;
36                 return ;
37             }
38         }
39     }
40 }
41 
42 int main ()
43 {
44     //freopen ("a.txt" , "r" , stdin ) ;
45     while (~ scanf ("%d%d" , &n , &m) ) {
46         E = 0 ;
47         flag = 0 ;
48         fill (head , head + n + 1 , -1 ) ;
49         while (m --) {
50             scanf ("%d%d%d" , &u , &v , &w) ;
51             add (u , v , w) ;
52         }
53         fill (vis , vis + n + 1 , 0) ;
54         vis[1] = 1 ;
55         sumxor[1] = 0 ;
56         dfs (1) ;
57         printf ("%s
" , flag ? "Yes" : "No" ) ;
58     }
59     return 0 ;
60 }

View Code

dfs树：
只要在ADG中进行广搜，只要有祖先和对应节点这种关系，那么他们就能构成环；反之若任意一对节点不符合这个原则，就不能构成环。（简单来说你能搜到就能成环）

此外nxt 存放的是 “边”。

因为用dfs找点只需 n 次，而用了邻接表找边只需 m 次。

又因为如果两个小环的异或值!= 0 , 那么所形成的的大环的异或值肯定！= 0 ；

所以总的复杂度为O（ｎ　＋　ｍ）。