题意：有2N个钥匙和M道门，每道门上有2个钥匙孔，只要打开一个即可。两个钥匙组成一个集合，共N个集合，集合中的一个钥匙被使用则另外一个钥匙会失效。求从前往后，最多能开几扇门。

分析：从集合元素为2易推断出是2-SAT的问题，但本题求最大的解决数，所以考虑二分求解。

一个集合中的钥匙a,b，若选a则必不选b；选b则必不选a。用2i和2i+1代表选第i个钥匙和不选第i个钥匙，加边a->b' , b->a'.

对于每道门，因为只要一个钥匙孔满足即可，构成的关系是析取，加边a'->b, b'->a。

二分能够开启的门数量，每次重新建图判断是否可行。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long LL;const int maxn =5e3+5;const int maxm = 1e5+5;struct Edge{    int v,next;  }edges[maxm<<1];int head[maxn],tot;stack
         
           S;int pre[maxn],low[maxn],sccno[maxn],dfn,scc_cnt;void init(){ tot = dfn = scc_cnt=0; memset(pre,0,sizeof(pre)); memset(sccno,0,sizeof(sccno)); memset(head,-1,sizeof(head)); while(!S.empty()) S.pop();}void AddEdge(int u,int v) { edges[tot] = (Edge){v,head[u]}; head[u] = tot++;}void Tarjan(int u){ int v; pre[u]=low[u]=++dfn; S.push(u); for(int i=head[u];~i;i=edges[i].next){ v= edges[i].v; if(!pre[v]){ Tarjan(v); low[u]=min(low[u],low[v]); } else if(!sccno[v]){ low[u]=min(low[u],pre[v]); } } if(pre[u]==low[u]){ int x; ++scc_cnt; for(;;){ x = S.top();S.pop(); sccno[x]=scc_cnt; if(x==u)break; } } }int N,M;int p1[maxn],p2[maxn];int key1[maxn],key2[maxn];bool check(int n){ init(); for(int i=1;i<=N;++i){ AddEdge(key1[i]*2,key2[i]*2+1); AddEdge(key2[i]*2,key1[i]*2+1); } for(int i =1;i<=n;++i){ AddEdge(p1[i]*2+1,p2[i]*2); AddEdge(p2[i]*2+1,p1[i]*2); } int all = 2*N; for(int i=0;i
          
           >1; if(check(mid)){ L = mid+1; ans = mid; } else R= mid-1; } printf("%d\n",ans); } return 0;}