Hướng dẫn giải của Mạng máy tính an toàn
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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 flashmt
#include <bits/stdc++.h> using namespace std; int n; vector <int> a[30000]; struct BiconnectedComponent { vector<int> low, num, s; vector< vector<int> > components; int counter; BiconnectedComponent() : num(n, -1), low(n, -1), counter(0) { for (int i = 0; i < n; i++) if (num[i] < 0) dfs(i, 1); } void dfs(int x, int isRoot) { low[x] = num[x] = ++counter; if (a[x].empty()) { components.push_back(vector<int>(1, x)); return; } s.push_back(x); for (int i = 0; i < a[x].size(); i++) { int y = a[x][i]; if (num[y] > -1) low[x] = min(low[x], num[y]); else { dfs(y, 0); low[x] = min(low[x], low[y]); if (isRoot || low[y] >= num[x]) { components.push_back(vector<int>(1, x)); while (1) { int u = s.back(); s.pop_back(); components.back().push_back(u); if (u == y) break; } } } } } }; int main() { int m, x, y; scanf("%d%d", &n, &m); while (m--) { scanf("%d%d", &x, &y); a[--x].push_back(--y); a[y].push_back(x); } BiconnectedComponent bc; int ans = 0; for (int i = 0; i < bc.components.size(); i++) ans = max(ans, int(bc.components[i].size())); printf("%d\n", ans); }
Code mẫu của happyboy99x
#include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<cstdio> #include<stack> using namespace std; #define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i) template<class T> void checkMin(T &a, const T &b) { if(b < a) a = b; } template<class T> void checkMax(T &a, const T &b) { if(b > a) a = b; } const int N = 3e4; vector<int> g[N]; int d[N], low[N], idx[N], ttime, n; void dfs(int u, int p, int &res, int &ncomp, stack<pair<int, int> > &st) { d[u] = low[u] = ttime++; TR(g[u], v) if(d[*v] == -1) { st.push(make_pair(u, *v)); dfs(*v, u, res, ncomp, st); checkMin(low[u], low[*v]); if(low[*v] >= d[u]) { int c = 0; while(true) { pair<int, int> e = st.top(); st.pop(); if(idx[e.first] != ncomp) ++c, idx[e.first] = ncomp; if(idx[e.second] != ncomp) ++c, idx[e.second] = ncomp; if(e == make_pair(u, *v)) break; } ++ncomp; checkMax(res, c); } } else if(*v != p && d[*v] < d[u]) { st.push(make_pair(u, *v)); checkMin(low[u], d[*v]); } } void solve() { memset(d, -1, sizeof d); memset(idx, -1, sizeof idx); stack<pair<int, int> > st; int res = 0, ncomp = 0; for(int u = 0; u < n; ++u) if(d[u] == -1) dfs(u, -1, res, ncomp, st); cout << max(res, 1) << endl; } void enter() { int m; cin >> n >> m; for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u; --v; g[u].push_back(v); g[v].push_back(u); } } int main() { ios::sync_with_stdio(false); enter(); solve(); return 0; }
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #include <climits> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) #define RESET(a, v) memset((a), (v), sizeof((a))) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int N = 30003; using namespace std; VI a[N]; int low[N], num[N]; int n, m, timer, ans; stack<II> s; void dfs(int u, int par) { num[u] = ++timer; low[u] = INT_MAX; TR(v, a[u]) if (*v != par) { if (num[*v]) low[u] = min(low[u], num[*v]); else { s.push(MP(u, *v)); dfs(*v, u); low[u] = min(low[u], low[*v]); if (low[*v] >= num[u]) { int cnt = 1; II edge; do { edge = s.top(); s.pop(); ++cnt; } while (edge != MP(u, *v)); ans = max(ans, cnt); } } } } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> m; int u, v; FOR(i, 0, m) { cin >> u >> v; a[u].PB(v); a[v].PB(u); } ans = 1; REP(i, 1, n) if (num[i] == 0) dfs(i, 0); cout << ans; return 0; }
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=30001; type list=^node; node=record u:longint; next:list; end; var f1,f2:text; stp,top,kq,count,n,m:longint; ke:array[1..MAXN] of list; stack,sl,father,low,num:array[1..MAXN] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure add(u:longint; var a:list); var p:list; begin new(p); p^.u:=u; p^.next:=a; a:=p; end; procedure inp; var i,u,v:longint; begin read(f1,n,m); for i:=1 to m do begin read(f1,u,v); add(u,ke[v]); add(v,ke[u]); end; end; procedure dfs(u:longint); var p:list; v,i,x:longint; begin inc(count); low[u]:=count; num[u]:=count; p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if num[v]=0 then begin father[v]:=u; inc(top); stack[top]:=v; dfs(v); low[u]:=min(low[u],low[v]); if low[v]>=num[u] then begin inc(stp); repeat x:=stack[top]; dec(top); inc(sl[stp]); until x=v; end; end else if v<>father[u] then low[u]:=min(low[u],num[v]); end; end; procedure solve; var i:longint; begin count:=0; kq:=0; top:=0; stp:=0; for i:=1 to n do if num[i]=0 then dfs(i); for i:=1 to n do kq:=max(kq,sl[i]+1); end; procedure ans; begin writeln(f2,kq); end; begin openF; inp; solve; ans; closeF; end.
Code mẫu của skyvn97
#include<cstdio> #include<stack> #include<vector> #define MAX 300300 #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; vector<int> g[MAX]; int low[MAX]; int num[MAX]; int ncp[MAX]; int p[MAX]; stack<ii> st; int m,n,nc,cnt,res; void minimize(int &x,const int &y) { if (x>y) x=y; } void maximize(int &x,const int &y) { if (x<y) x=y; } void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); REP(i,m) { int u,v; scanf("%d",&u); scanf("%d",&v); g[u].push_back(v); g[v].push_back(u); } } void visit(int u) { cnt++; low[u]=n+7; num[u]=cnt; FORE(it,g[u]) { int v=*it; if (num[v]==0) { p[v]=u; st.push(ii(u,v)); visit(v); minimize(low[u],low[v]); if (low[v]>=num[u]) { int sz=0; int x,y; nc++; do { x=st.top().fi; y=st.top().se; st.pop(); if (ncp[x]!=nc) sz++; if (ncp[y]!=nc) sz++; ncp[x]=nc; ncp[y]=nc; } while (x!=u || y!=v); maximize(res,sz); } } else if (v!=p[u] && num[v]<num[u]) { st.push(ii(u,v)); minimize(low[u],num[v]); } } } void process(void) { if (m==0) { printf("1"); return; } FOR(i,1,n) if (num[i]==0) visit(i); printf("%d",res); } int main(void) { loadgraph(); process(); return 0; }
Bình luận