Editorial for Mạng máy tính an toàn
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 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; }
Comments