拓扑排序&&欧拉（回）路

摘要：最近是不适合写代码么?忘记初始化wa到死<_=_=_>。唔--最近在学习图论，从基础搞起，先搞了拓扑排序和欧拉（回）路。

Part 0. 拓扑排序

　　==挖坑==

Part 1. 欧拉（回）路

先判连通性

欧拉回路：

有向图：每个顶点入度等于出度
无向图：每个顶点度数都为偶数

欧拉路：

有向图：每个顶点入度等于出度，或者，一个顶点入度比出度大一，一个顶点入度比出度小一（起点），其余顶点入度等于出度
无向图：每个顶点度数都为偶数，或者，只有两个顶点度数为奇数

HDU 3018 Ant Trip 注意hint

　　哇~我要贴错误代码啦~~说不定还能坑一下自己~_~

 #include <iostream>

 #include <stdio.h>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <map>

 using namespace std ;

 #define rep(i,n) for (int i = 1 ; i <= n ; ++ i)

 #define lson (i<<1)

 #define rson (i<<1|1)

 const int maxn =  ;

 vector<int> G[maxn] ;

 int N , R , du[maxn] , cnt , fa[maxn] , num ;

 bool vis[maxn] ;

 void dfs(int rt)

 {

     if (vis[rt]) return ;

     num ++ ;

     cnt += (du[rt]&) ;

     vis[rt] = true ;

     int v ;

     for (int i =  ; i < G[rt].size() ; ++ i) {

         v = G[rt][i] ;

         if (v != fa[rt]) {

             fa[v] = rt ;

             dfs(v) ;

         }

     }

 }

 int main()

 {

     int u , v ;

     while (scanf("%d%d",&N,&R) == ) {

         memset(vis,false,sizeof(vis)) ;

         memset(fa,-,sizeof(fa)) ;

         rep(i,N) G[i].clear() ;

         rep(i,R) {

             scanf("%d%d",&u,&v) ;

             du[u] ++ , du[v] ++ ;

             G[u].push_back(v) ;

             G[v].push_back(u) ;

         }

         int ans =  ;

         rep(i,N) {

             if (!vis[i]) {

                 fa[i] = - ;

                 cnt = num =  ;

                 dfs(i) ;

                 if (num == ) continue ;

                 if (cnt == ) ans ++ ;

                 else ans += (cnt/) ;

             }

         }

         printf("%d\n",ans) ;

     }

     return  ;

 }

haha

路径什么的待补~~~~~

==end==

秒客网

拓扑排序&&欧拉（回）路

相关文章