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.

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

Please read the guidelines before commenting.


There are no comments at the moment.