还有两个月就NOIP了我居然还在敲这种东西.........
洛谷 P5318 DFS BFS 模版题
复习一下 DFS:
从第一个节点开始搜 用vis数组记忆化 搜到每一个点时 如果没搜过 就把他标记 并搜他所能到达的节点 直至不能再搜为止 复杂度O(V+E) 最坏复杂度Q(n!) ;
复习一下BFS:
从第一个节点开始搜 用vis数组记忆化 同时开一个队列 先将第一个节点入队 然后将他的每一个能到达的点都入队 在队列中进行搜索 如果队首没有搜过 就标记 然后重复上述步骤存入所能到达的节点 然后将队首出队 直至队列为空
题很简单 就是板子 注意排序 (然而是本蒟蒻第一次用邻接表存图){
1 #include <iostream> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstdio> 5 #include <climits> 6 #include <cassert> 7 #include <cstring> 8 #include <cstdlib> 9 #include <cctype> 10 #include <iomanip> 11 #include <utility> 12 #include <set> 13 #include <map> 14 #include <list> 15 #include <stack> 16 #include <queue> 17 #include <deque> 18 #include <vector> 19 #include <bitset> 20 #include <ctime> 21 #define int long long 22 #define ll long long 23 #define ull unsigned long long 24 #define re register 25 #define mod1 998244353 26 #define mod2 100000007 27 #define lowbit(x) x & (-x) 28 #define gcd(a,b) __gcd(a,b) 29 #define mid ((l + r) >> 1) 30 #define rep(i,a,b) for(re int i(a);i <= b;++ i) 31 #define rrep(i,a,b) for(re int i(a);i >= b;i --) 32 using namespace std; 33 inline int read() { 34 re int x = 0,f = 1; 35 re char ch = getchar(); 36 while(ch < '0' || ch > '9') { 37 if(ch == '-') f = -1; 38 ch = getchar(); 39 } 40 while(ch >= '0' && ch <= '9') { 41 x = (x << 3) + (x << 1) + (ch ^ 48); 42 ch = getchar(); 43 } 44 return x * f; 45 } 46 //#define OJ 47 //#define debug 48 const int M = 1e5 + 1; 49 vector<int> v[M]; 50 bool vis[M]; 51 queue<int> q; 52 inline void dfs(int u) { 53 vis[u] = 1; 54 cout << u << " "; 55 rep(i,0,v[u].size() - 1) { 56 if(v[u].size() == 0) break; 57 if(v[u][i]) { 58 if(!vis[v[u][i]]) dfs(v[u][i]); 59 } 60 } 61 } 62 inline void bfs(int u) { 63 q.push(u); 64 vis[u] = 1; 65 cout << u << " "; 66 while(!q.empty()) { 67 int t = q.front(); 68 rep(i,0,v[t].size() - 1) { 69 if(v[t].size() == 0) break; 70 if(v[t][i]) { 71 if(!vis[v[t][i]]) q.push(v[t][i]),cout << v[t][i] << " ",vis[v[t][i]] = 1; 72 } 73 } 74 q.pop(); 75 } 76 } 77 signed main() { 78 #ifdef OJ 79 freopen(".in","r",stdin); 80 freopen(".out","w",stdout); 81 #endif 82 int n = read(); 83 int m = read(); 84 rep(i,1,m) { 85 re int x = read(); 86 re int y = read(); 87 v[x].push_back(y); 88 } 89 rep(i,1,n) sort(v[i].begin(),v[i].end()); 90 dfs(1); 91 cout << endl; 92 memset(vis,false,sizeof(vis)); 93 bfs(1); 94 #ifdef debug 95 printf("\nTime used = %lf", (double)clock() / CLOCKS_PER_SEC); 96 #endif 97 return 0; 98 }
Cause‘ nothing lasts forever, but cold november rain..
标签:图论,ch,NOIP,int,long,re,遍历,include,define From: https://www.cnblogs.com/Eruption/p/16744551.html