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

Download