Editorial for VM 14 Bài 18 - Cây khung
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> #define X first #define Y second const int N = 2000; using namespace std; struct disjoint_set { int P[N]; disjoint_set() {for(int i = 0; i < N; i++) P[i] = i;} int at(int x) {return (x == P[x]) ? P[x] : (P[x] = at(P[x]));} void join(int x, int y) {P[at(x)] = at(y);} } DS; int id[N][N]; vector<int> a[N]; int T[N]; bool inST[N], was[N], con[N][N]; ii e[N]; int n, m; void DFS(int u) { was[u] = true; int i, v; for(i = 0; i < a[u].size(); i++) { v = a[u][i]; if (!was[v] && con[u][v]) { T[v] = u; DFS(v); } } } void PRINT() { for(int i = 1; i <= m; i++) if (inST[i]) printf("%d %d\n", e[i].X, e[i].Y); } int main() { scanf("%d %d", &n, &m); int i, x, y; for(i = 1; i <= m; i++) { scanf("%d %d", &e[i].X, &e[i].Y); a[e[i].X].push_back(e[i].Y); a[e[i].Y].push_back(e[i].X); id[e[i].X][e[i].Y] = id[e[i].Y][e[i].X] = i; } int cnt = 0; for(i = 1; i <= m; i++) { x = DS.at(e[i].X); y = DS.at(e[i].Y); if (x != y) { con[e[i].X][e[i].Y] = con[e[i].Y][e[i].X] = true; inST[i] = true; DS.join(x, y); cnt++; } if (cnt == n - 1) break; } printf("3\n"); PRINT(); for(i = 1; i <= m; i++) if (!inST[i]) { inST[i] = true; con[e[i].X][e[i].Y] = con[e[i].Y][e[i].X] = false; int s = e[i].X, t = e[i].Y; DFS(s); inST[id[T[t]][t]] = false; PRINT(); inST[id[T[t]][t]] = true; inST[id[T[T[t]]][T[t]]] = false; PRINT(); break; } return 0; }
Code mẫu của RR
#include <iostream> #include <algorithm> #include <vector> #include <cstring> using namespace std; vector<int> ke[1011]; int n, m, cnt; int father[1011], getIn[1011], getOut[1011]; bool visited[1011], hasSolution = false; int lab[1011]; int getRoot(int u) { if (lab[u] < 0) return u; else return lab[u] = getRoot(lab[u]); } void merge(int u, int v) { u = getRoot(u); v = getRoot(v); lab[u] += lab[v]; lab[v] = u; } vector<int> cycle; bool inCycle[1011]; void find(int x) { memset(lab, -1, sizeof lab); for(int i = 0; i < cycle.size(); ++i) if (i != x) { int j = (i + 1) % cycle.size(); int u = cycle[i], v = cycle[j]; if (getRoot(u) != getRoot(v)) { cout << u << ' ' << v << endl; merge(u, v); } } for(int u = 1; u <= n; ++u) { for(int i = 0; i < ke[u].size(); ++i) { int v = ke[u][i]; if (getRoot(u) != getRoot(v)) { cout << u << ' ' << v << endl; merge(u, v); } } } } void dfs(int u) { getIn[u] = ++cnt; visited[u] = true; for(int i = 0; i < ke[u].size(); ++i) { int v = ke[u][i]; if (v == father[u]) continue; if (!visited[v]) { father[v] = u; dfs(v); } else { if (!getOut[v]) { cycle.push_back(v); inCycle[v] = true; int x = u; while (!inCycle[x]) { cycle.push_back(x); inCycle[x] = true; x = father[x]; } if (!hasSolution) { hasSolution = true; cout << 3 << endl; find(0); find(1); find(2); } } } } getOut[u] = ++cnt; } int main() { cin >> n >> m; for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; ke[u].push_back(v); ke[v].push_back(u); } dfs(1); }
Code mẫu của skyvn97
#include<cstdio> #include<queue> #include<vector> #define MAX 2222 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define REP(i,n) for (int i=0;i<(n);i=i+1) #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) #define fi first #define se second using namespace std; typedef pair<int,int> ii; inline int nextInt(void) { int x; scanf("%d",&x); return (x); } class DSU { private: vector<int> up; int find(int x) { if (up[x]<0) return (x); up[x]=find(up[x]); return (up[x]); } public: DSU() {} DSU(int n) { up.assign(n+7,-1); } bool join(int a,int b) { int x=find(a); int y=find(b); if (x==y) return (false); up[y]=x; return (true); } }; ii edge[MAX]; vector<int> g[MAX]; vector<int> cyc; int n,m; bool vst[MAX]; int p[MAX]; void loadgraph(void) { n=nextInt(); m=nextInt(); FOR(i,1,m) { int u=nextInt(); int v=nextInt(); edge[i]=ii(u,v); g[u].push_back(i); g[v].push_back(i); } } void bfs(int s,int f,int blk) { queue<int> q; vst[s]=true; q.push(s); while (!q.empty()) { int u=q.front();q.pop(); if (u==f) return; FORE(it,g[u]) if (*it!=blk) { int v=edge[*it].fi^edge[*it].se^u; if (!vst[v]) { vst[v]=true; p[v]=*it; q.push(v); } } } } void trace(int s,int t) { while (t!=s) { cyc.push_back(p[t]); t=edge[p[t]].fi^edge[p[t]].se^t; } } void findcycle(void) { DSU dsu=DSU(n); FOR(i,1,m) if (!dsu.join(edge[i].fi,edge[i].se)) { int u=edge[i].fi; int v=edge[i].se; bfs(u,v,i); trace(u,v); cyc.push_back(i); return; } } void findtree(int id) { DSU dsu=DSU(n); REP(i,cyc.size()) if (i!=id) { int u=edge[cyc[i]].fi; int v=edge[cyc[i]].se; printf("%d %d\n",u,v); dsu.join(u,v); } FOR(i,1,m) { int u=edge[i].fi; int v=edge[i].se; if (dsu.join(u,v)) printf("%d %d\n",u,v); } } void process(void) { printf("3\n"); REP(i,3) findtree(i); } int main(void) { loadgraph(); findcycle(); process(); return 0; }
Comments