SAFENET2 - Mạng máy tính an toàn

Tác giả: flashmt

Ngôn ngữ: C++

#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);
}

Download