SAFENET2 - Mạng máy tính an toàn
Tác giả: happyboy99x
Ngôn ngữ: C++
#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;
}