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