图的遍历 洛谷P2661(并查集求有向图最小环) 也放在并查集那一章里了,装作刷题很多的样子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 #include <cstdio> #include <algorithm> using namespace std;const int MAX_N = 2e5 + 2 ;int par[MAX_N];int d[MAX_N];int n;int ans = 2e9 ;void init () { for (int i = 0 ; i <= n; ++i) { par[i] = i; d[i] = 0 ; } } int find (int x) { if (x == par[x]) return x; else { int last= par[x]; par[x] = find (par[x]); d[x] += d[last]; } return par[x]; } bool same (int x, int y) { return find (x) == find (y); } void unite (int x, int y) { x = find (x); y = find (y); if (x == y) return ; else par[x] = y; } void solve (int a, int b) { int x = find (a); int y = find (b); if (x == y) ans = min (ans, d[a] + d[b] + 1 ); else { unite (x, y); d[a] = d[b] + 1 ; } } int main () { scanf ("%d" , &n); init (); for (int i = 1 ; i <= n; ++i) { int t; scanf ("%d" , &t); solve (i, t); } printf ("%d\n" , ans); return 0 ; }
洛谷P1330(染色+bfs求连通块数量+思路) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 #include <cstdio> #include <queue> using namespace std;const int MAX_N = 1e4 + 1 ;const int MAX_M = 1e5 + 1 ;bool maze[MAX_N][MAX_N];int d[MAX_N];int used[MAX_N];int n, m;int res1 = 0 ;int res2 = 0 ;int ans = 0 ;int possiable = 1 ;queue<int > que; void bfs (int x) { que.push (x); d[x] = 0 ; while (!que.empty ()) { int t = que.front (); que.pop (); for (int i = 1 ; i <= n; ++i) { if (maze[t][i]) { if (d[i] == -1 ) { d[i] = !d[t]; que.push (i); } else { if (d[t] == d[i]) { possiable = 0 ; return ; } } } } } } int main () { scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= n; ++i) d[i] = -1 ; for (int i = 1 ; i <= m; ++i) { int a, b; scanf ("%d%d" , &a, &b); maze[a][b] = maze[b][a] = 1 ; } for (int i = 1 ; i <= n; ++i) { if (d[i] == -1 ) { possiable = 1 ; res1 = 0 ; res2 = 0 ; bfs (i); if (!possiable) { printf ("Impossible\n" ); return 0 ; } for (int i = 1 ; i <= n; ++i) { if (d[i] == -1 || used[i]) continue ; if (d[i] == 1 ) res1++; else if (!d[i]) res2++; used[i] = 1 ; } ans += min (res1, res2); } } printf ("%d\n" , ans); return 0 ; }
洛谷P1341(欧拉回路问题+并查集) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 #include <cstdio> int n;int par[130 ];int deg[130 ];int G[130 ][130 ];char ans[1500 ];char a[3 ];int head = 0 ;int find (int x) { if (x == par[x]) return x; else return par[x] = find (par[x]); } void euler (int u) { for (int v = 64 ; v <= 125 ; ++v) if (G[u][v]) { G[u][v] = G[v][u] = 0 ; euler (v); } ans[n--] = u; } int main () { scanf ("%d" , &n); for (int i = 64 ; i <= 125 ; i++) par[i] = i; for (int i = 1 ; i <= n; i++) { scanf ("%s" , a); G[a[0 ]][a[1 ]] = G[a[1 ]][a[0 ]] = 1 ; deg[a[0 ]]++; deg[a[1 ]]++; int x = find (a[0 ]); int y = find (a[1 ]); par[x] = y; } int cnt = 0 ; for (int i = 64 ; i <= 125 ; i++) if (par[i] == i && deg[i]) cnt++; if (cnt > 1 ) { printf ("No Solution\n" ); return 0 ; } cnt = 0 ; head = 0 ; for (int i = 64 ; i <= 125 ; i++) { if (deg[i] & 1 ) { cnt++; if (!head) head = i; } } if (cnt && cnt != 2 ) { printf ("No Solution\n" ); return 0 ; } if (!head) for (int i = 64 ; i <= 125 ; i++) if (deg[i]) { head = i; break ; } euler (head); printf ("%s\n" , ans); return 0 ; }
洛谷P2921(有向图成环+步数) 大概是照着题解默了一遍,早上9:00写到14:30不带停的,还是实现不了,实在饿得受不了就偷懒了~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include <cstdio> #include <algorithm> using namespace std;const int MAX_N = 1e5 + 1 ;int n;int G[MAX_N];int color[MAX_N];int sizec[MAX_N];int sucdfn[MAX_N];int dfn[MAX_N];void init () { scanf ("%d" , &n); for (int i = 1 ; i <= n; ++i) { scanf ("%d" , &G[i]); } } void solve () { for (int cow = 1 ; cow <= n; ++cow) { for (int i = cow, cnt = 0 ; ; i = G[i], ++cnt) { if (!color[i]) { color[i] = cow; dfn[i] = cnt; } else if (color[i] == cow) { sizec[cow] = cnt - dfn[i]; sucdfn[cow] = dfn[i]; printf ("%d\n" , cnt); break ; } else { sizec[cow] = sizec[color[i]]; sucdfn[cow] = cnt + max (sucdfn[color[i]] - dfn[i], 0 ); printf ("%d\n" , sucdfn[cow] + sizec[cow]); break ; } } } } int main () { init (); solve (); return 0 ; }
最短路算法 洛谷P1339(Dijistra板子题) 我不会说我板子题都WA、RE了的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include <cstdio> #include <algorithm> using namespace std;const int MAX_C = 2501 ;const int MAX_T = 6201 ;const int INF = 1e9 ;int C, T, Ts, Te;int cost[MAX_T][MAX_T];int dis[MAX_T];int vis[MAX_T];void init () { scanf ("%d%d%d%d" , &T, &C, &Ts, &Te); for (int i = 1 ; i <= T; ++i) { for (int j = 1 ; j <= T; ++j) { cost[i][j] = INF; } dis[i] = INF; vis[i] = false ; } for (int i = 1 ; i <= C; ++i) { int a, b, c; scanf ("%d%d%d" , &a, &b, &c); cost[a][b] = cost[b][a] = c; } for (int i = 1 ; i <= T; ++i) dis[i] = cost[Ts][i]; dis[Ts] = 0 ; vis[Ts] = 1 ; } void Dijistra () { for (int i = 1 ; i <= T; ++i) { int x, m = INF; for (int y = 1 ; y <= T; ++y) if (!vis[y] && dis[y] <= m) m = dis[x = y]; vis[x] = 1 ; for (int y = 1 ; y <= T; ++y) dis[y] = min (dis[y], dis[x] + cost[x][y]); } } int main () { init (); Dijistra (); printf ("%d\n" , dis[Te]); return 0 ; }