Prelude

好，HAOI2017终于会做一道题了！

传送到洛谷：

传送到LOJ：

本篇博客链接：

---

Solution

首先要读懂题。

考场上我是这样想的。

我们把每个城市看作一个点，在“当前没有贸易关系”的城市之间连边。

此时，如果一个城市集合是一个城市群，那么这个城市集合中的任意两个城市之间都没有边。

因为“可以划分为两个城市群”，所以这个图是个二分图。

那么“最大城市群”就是二分图的最大独立集。

“在两个城市之间建立贸易关系”即删除这两个点之间的边。

所以题目实际上是，给一个二分图，问删掉哪些边之后，最大独立集的大小会增加。

考虑如何求最大独立集大小。

最大独立集大小=总点数-最小覆盖集大小=最大匹配数。

也就是说，这个题问的是，给一个二分图，问删掉哪些边之后，最大匹配的数量会减少，也就是问，哪些边一定在最大匹配里。

这个时候，我们已经得到了50分做法了。

先建出网络流，求出最大匹配数量，然后删掉一条边重新跑一次，看最大匹配是否减少，就是我考场上的做法。

用退流可以做到更优越的复杂度，但好像过不了n=500的点？

接下来考虑满分做法。

考虑如下定理：若一条边一定在最大匹配中，则在最终的残量网络中，这条边一定满流，且这条边的两个顶点一定不在同一个强连通分量中。

证明也很简单：首先满流的要求是很显然的，其次，如果这两个点在同一个强连通分量中，那么一定有一个环经过这条边，沿着环增广一下，网络仍然满足流量限制，但是这条边就不满流了，于是就得到了一组新的最大匹配。

所以只要跑完Dinic跑Tarjan就好了。

---

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef pair
           
             pii;const int MAXN = 10010;const int MAXM = 150010;const int MAXV = 100010;const int MAXE = 1000010;const int INF = 0x3f3f3f3f;int _w;int n, m, uu[MAXM], vv[MAXM];namespace G { int head[MAXN], nxt[MAXM<<1], to[MAXM<<1], eid; void init() { eid = 0; memset(head, -1, sizeof head); } void adde( int u, int v ) { to[eid] = v, nxt[eid] = head[u], head[u] = eid++; to[eid] = u, nxt[eid] = head[v], head[v] = eid++; }}namespace Dinic { struct Edge { int u, v, c, f; Edge() {} Edge( int u, int v, int c, int f ): u(u), v(v), c(c), f(f) {} }; int n, m, s, t; int head[MAXV], nxt[MAXE<<1]; Edge edge[MAXE<<1]; int dis[MAXV], cur[MAXV]; queue
            
              q; void init( int _n ) { n = _n, m = 0; for( int i = 0; i < n; ++i ) head[i] = -1; } int adde( int u, int v, int c ) { int eid = m; edge[m] = Edge(u, v, c, 0); nxt[m] = head[u], head[u] = m++; edge[m] = Edge(v, u, 0, 0); nxt[m] = head[v], head[v] = m++; return eid; } bool bfs() { for( int i = 0; i < n; ++i ) dis[i] = INF; dis[s] = 0, q.push(s); while( !q.empty() ) { int u = q.front(); q.pop(); for( int i = head[u]; ~i; i = nxt[i] ) { Edge &e = edge[i]; if( e.c > e.f && dis[e.v] == INF ) { dis[e.v] = dis[u] + 1; q.push(e.v); } } } return dis[t] != INF; } int dfs( int u, int res ) { if( u == t || !res ) return res; int flow = 0; for( int &i = cur[u]; ~i; i = nxt[i] ) { Edge &e = edge[i]; if( e.c > e.f && dis[e.v] == dis[u] + 1 ) { int f = dfs( e.v, min(res, e.c-e.f) ); flow += f, res -= f; e.f += f, edge[i^1].f -= f; if( !res ) break; } } return flow; } int solve( int _s, int _t ) { s = _s, t = _t; int flow = 0; while( bfs() ) { for( int i = 0; i < n; ++i ) cur[i] = head[i]; flow += dfs(s, INF); } return flow; }}namespace Bipartite { int color[MAXN], eid[MAXM]; queue
             
               q; void bfs( int s ) { using namespace G; color[s] = 0, q.push(s); while( !q.empty() ) { int u = q.front(); q.pop(); for( int i = head[u]; ~i; i = nxt[i] ) { int v = to[i]; if( color[v] == -1 ) { color[v] = !color[u]; q.push(v); } } } } void bipartite() { for( int i = 1; i <= n; ++i ) color[i] = -1; for( int i = 1; i <= n; ++i ) if( color[i] == -1 ) bfs(i); int s = 0, t = n+1; Dinic::init(t+1); for( int i = 1; i <= n; ++i ) if( color[i] ) Dinic::adde(s, i, 1); else Dinic::adde(i, t, 1); for( int i = 0; i < m; ++i ) if( color[uu[i]] ) eid[i] = Dinic::adde( uu[i], vv[i], 1 ); else eid[i] = Dinic::adde( vv[i], uu[i], 1 ); Dinic::solve(s, t); }}using Bipartite::bipartite;namespace Tarjan { using namespace Dinic; int dfn[MAXV], low[MAXV], scc[MAXV], dfnc, sccc; stack
              
                stk; void dfs( int u ) { dfn[u] = low[u] = ++dfnc; stk.push(u); for( int i = head[u]; ~i; i = nxt[i] ) { Edge &e = edge[i]; if( e.c == e.f ) continue; int v = e.v; if( !dfn[v] ) { dfs(v); low[u] = min( low[u], low[v] ); } else if( !scc[v] ) { low[u] = min( low[u], dfn[v] ); } } if( low[u] == dfn[u] ) { ++sccc; while(1) { int o = stk.top(); stk.pop(); scc[o] = sccc; if( o == u ) break; } } } void tarjan() { dfnc = sccc = 0; for( int i = 0; i < Dinic::n; ++i ) if( !dfn[i] ) dfs(i); }}using Tarjan::tarjan;namespace Solve { vector
               
                 ans; void solve() { using Dinic::Edge; using Dinic::edge; using Tarjan::scc; using Bipartite::eid; for( int i = 0; i < m; ++i ) { Edge &e = edge[eid[i]]; if( e.c != e.f ) continue; int u = e.u, v = e.v; if( u > v ) swap(u, v); if( scc[u] == scc[v] ) continue; ans.push_back( pii(u, v) ); } sort(ans.begin(), ans.end()); printf( "%lu\n", ans.size() ); for( int i = 0; i < (int)ans.size(); ++i ) printf( "%d %d\n", ans[i].first, ans[i].second ); }}using Solve::solve;int main() { _w = scanf( "%d%d", &n, &m ); G::init(); for( int i = 0; i < m; ++i ) { _w = scanf( "%d%d", uu+i, vv+i ); G::adde( uu[i], vv[i] ); } bipartite(); tarjan(); solve(); return 0;}