REFORM spoj – VOI 2015 – Kế hoạch cải tổ

input 4 4 1 2 2 3 2 4  3 4  output 8

inout 7 5 1 2 3 4 5 6 5 7 6 7 output 0

#include <bits/stdc++.h> using namespace std; #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 ll long long #define pb push_back #define getbit(x, pos) ((x >> (pos - 1)) & 1) #define sz(x) (int)x.size() const int Nmax = 100100; vector<int> ad[Nmax]; int n, m, c1 = 0, cnt = 0, num[Nmax], low[Nmax], child[Nmax], root, Count, bridge; bool Free[Nmax]; // DFS để đếm thành phần liên thông cũng như tìm các cầu. void visit(int p, int i) { if (Count == 1) c1++; num[i] = ++cnt; low[i] = num[i]; child[i] = 1; Free[i] = 1; FOR(j, 0, sz(ad[i]) - 1) if (ad[i][j] != p) { if (Free[ad[i][j]] == 0) { visit(i, ad[i][j]); child[i] += child[ad[i][j]]; low[i] = min(low[i], low[ad[i][j]]); } else low[i] = min(low[i], num[ad[i][j]]); } if (root != i && low[i] == num[i]) bridge++; } int main() { cin >> n >> m; FOR(i, 1, m) { int x, y; cin >> x >> y; ad[x].pb(y); ad[y].pb(x); } Count = 0; memset(Free, 0, sizeof Free); FOR(i, 1, n) if (Free[i] == 0) { root = i; Count++; visit(0, i); } // trường hợp đồ thị có >= 3 thành phần liên thông, kết quả là 0 if (Count >= 3) { cout << 0; return 0; } ll res; if (Count == 2) { // trường hợp đầu tiên. res = (ll)(m - bridge) * c1 * (n - c1); } else { res = (ll)(m - bridge) * ((ll)n * (n - 1)/2 - m); // cố định cầu bằng cách cố đỉnh các đỉnh từ 2 tới n và cha của các đỉnh tương ứng. // low[i] == num[i] nghĩa là i - cha[i] là cầu FOR(i, 2, n) if (low[i] == num[i]) res += (ll)child[i] * (n - child[i]) - 1; } cout << res; return 0; }

const fi='; nmax=1000000; mmax=400000; type data=longint; var f:text; adj,x,y:array[0..mmax+1] of data; head:array[0..nmax+1] of data; sl:array[0..nmax+1] of int64; low,num,tr:array[0..nmax+1] of data; n,m,dinh,lab,sl1,res,khop,cau:int64; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); read(f,n,m); for i:=0 to n+1 do head[i]:=0; for i:=1 to m do begin read(f,x[i],y[i]); inc(head[x[i]]); inc(head[y[i]]); end; for i:=1 to n+1 do head[i]:=head[i-1]+head[i]; for i:=1 to m do begin adj[head[x[i]]]:=y[i]; dec(head[x[i]]); adj[head[y[i]]]:=x[i]; dec(head[y[i]]); end; close(f); end; function min(a,b:data):data; begin if a<b then exit(a); exit(b); end; procedure dfs(u:data); var v,k,i:data; s:boolean; begin inc(lab); low[u]:=lab; num[u]:=lab; k:=0; sl[u]:=1; s:=false; for v:=head[u]+1 to head[u+1] do if tr[u]<>adj[v] then begin if num[adj[v]]=0 then begin tr[adj[v]]:=u; inc(k); dfs(adj[v]); if low[adj[v]]>=num[u] then s:=true; sl[u]:=sl[adj[v]]+sl[u]; low[u]:=min(low[u],low[adj[v]]); end else low[u]:=min(low[u],num[adj[v]]); end; if ((s and (tr[u]<>0)) or ((tr[u]=0) and (k>1))) then inc(khop); if (Low[u]=num[u]) and (tr[u]<>0) then inc(cau); end; procedure ddfs(u:data); var v:data; begin inc(dinh); num[u]:=1; for v:=head[u]+1 to head[u+1] do if num[adj[v]]=0 then ddfs(adj[v]); end; procedure xuli; var i,j:data; stplt:int64; begin for i:=1 to n do num[i]:=0; stplt:=0; sl1:=0; for i:=1 to n do if num[i]=0 then begin dinh:=0; ddfs(i); if sl1=0 then sl1:=dinh; inc(stplt); end; if stplt>2 then begin writeln('0'); exit; end; for i:=1 to n do num[i]:=0; tr:=num; cau:=0; khop:=0; lab:=0; for i:=1 to n do if num[i]=0 then dfs(i); if stplt=1 then begin res:=(m-cau)*((n*(n-1)) div 2 - m); for i:=2 to n do if low[i]=num[i] then res:=res+int64(sl[i])*(int64(n-sl[i]))-1; writeln(res); exit; end; if stplt=2 then begin res:=(m-cau)*sl1*(n-sl1); writeln(res); end; end; begin docfile; xuli; end.