1 //想了很久，发现自己做这道题时犯了一个大BUG。我的思路是，把一组钥匙看成一对X,-X。把  2 //门确定的关系连边。其实这样是有错的，因为边的意义是“必须”，而实际上，门确定的只是矛盾  3 //关系。不是必须是，不是门上锁其中一个选或不选就能影响到另一个。   4   5 #include <iostream>  6 #include <cstdio>  7 #include <cstring>  8 #include <algorithm>  9 using namespace std; 10  11 const int MAXN=3200; 12 const int MAXM=8000; 13  14 int bel[MAXN],head[MAXN],dfn[MAXN],low[MAXN],st[MAXN],stop,index,tot; 15 int belong[MAXN],pat; 16 bool stack[MAXN]; 17  18 struct { 19     int u,v; 20     int next,Id; 21 }edge[MAXM]; 22 int n,m; 23  24 void addedge(int u,int v){ 25     edge[tot].u=u; 26     edge[tot].v=v; 27     edge[tot].Id=tot; 28     edge[tot].next=head[u]; 29     head[u]=tot++; 30 } 31  32 void init(){ 33     for(int i=0;i<n*2;i++){ 34         dfn[i]=low[i]=0; 35         stack[i]=false; 36         belong[i]=-1; 37     } 38     stop=0; index=0; pat=-1; 39 } 40  41 void tarjan(int u,int limited){ 42     int v; 43     dfn[u]=low[u]=++index; 44     st[stop++]=u; 45     stack[u]=true; 46     for(int e=head[u];e!=-1;e=edge[e].next){ 47         if(edge[e].Id<=limited){ 48             v=edge[e].v; 49             if(dfn[v]==0){ 50                 tarjan(v,limited); 51                 low[u]=min(low[u],low[v]); 52             } 53             else if(stack[v]){ 54                 low[u] = min(low[u], dfn[v]); 55             } 56         } 57     } 58     if(dfn[u]==low[u]){ 59         pat++; 60         do{ 61             v=st[--stop]; 62             stack[v]=false; 63             belong[v]=pat; 64         }while(u!=v); 65     } 66 } 67  68 bool slove(int mid){ 69     init(); 70     for(int i=0;i<2*n;i++){ 71         if(dfn[i]==0){ 72             tarjan(i,mid); 73         } 74     } 75     bool flag=true; 76     for(int i=0;i<n;i++){ 77         if(belong[i]==belong[2*i+1]){ 78             flag=false; 79             break; 80         } 81     } 82     return flag; 83 } 84  85 int main(){ 86     int u,v,t; int s1,s2; 87     while(scanf("%d%d",&n,&m)!=EOF){ 88         if(n==0&&m==0) break; 89         for(int i=0;i<=2*n;i++) 90         head[i]=-1; 91         tot=1; 92         for(int i=0;i<n;i++){ 93             scanf("%d%d",&u,&v); 94             bel[u]=2*i; bel[v]=2*i+1; 95         } 96         for(int i=1;i<=m;i++){ 97             scanf("%d%d",&u,&v); 98             s1=bel[u]; s2=bel[v]; 99             addedge(s1^1,s2);100             addedge(s2^1,s1);101         }102         int lown,high,mid;103         lown=1;high=m; int ans;104         while(lown<=high){105             mid=(lown+high)/2;106             if(slove(mid*2)){107             //    cout<<mid<<endl;108                 ans=mid; lown=mid+1;109             }110             else high=mid-1;111         }112         printf("%d\n",ans);113     }114     return 0;115 }

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <vector>  6 #include <queue>  7 #define MAXN 5005  8 #define MAXM 50005  9 #define INF 1000000000 10 using namespace std; 11 struct Edge 12 { 13     int v, next; 14 }edge[MAXM]; 15 int n, m, e; 16 int top, scc, index; 17 int low[MAXN], dfn[MAXN], instack[MAXN]; 18 int head[MAXN], st[MAXN], fa[MAXN]; 19 int a[MAXN], b[MAXN], hash[MAXN]; 20 int x[MAXN], y[MAXN]; 21 void init() 22 { 23     top = scc = index = e = 0; 24     memset(head, -1, sizeof(head)); 25     memset(dfn, 0, sizeof(dfn)); 26     memset(instack, 0, sizeof(instack)); 27 } 28 void insert(int x, int y) 29 { 30     edge[e].v = y; 31     edge[e].next = head[x]; 32     head[x] = e++; 33 } 34 void tarjan(int u) 35 { 36     low[u] = dfn[u] = ++index; 37     instack[u] = 1; 38     st[++top] = u; 39     int v; 40     for(int i = head[u]; i != -1; i = edge[i].next) 41     { 42         v = edge[i].v; 43         if(!dfn[v]) 44         { 45             tarjan(v); 46             low[u] = min(low[u], low[v]); 47         } 48         else if(instack[v]) low[u] = min(low[u], dfn[v]); 49     } 50     if(dfn[u] == low[u]) 51     { 52         scc++; 53         do 54         { 55             v = st[top--]; 56             instack[v] = 0; 57             fa[v] = scc; 58         }while(v != u); 59     } 60 } 61 bool check(int n) 62 { 63     for(int i = 1; i <= n; i++) 64         if(fa[i] == fa[i + n]) return false; 65     return true; 66 } 67 void build(int bound) 68 { 69     init(); 70     for(int i = 1; i <= n; i++) 71     { 72         insert(a[i], b[i] + 2 * n); 73         insert(b[i], a[i] + 2 * n); 74     } 75     for(int i = 1; i <= bound; i++) 76     { 77         insert(x[i] + 2 * n, y[i]); 78         insert(y[i] + 2 * n, x[i]); 79     } 80     for(int i = 1; i <= 2 * n; i++) 81         if(!dfn[i]) tarjan(i); 82 } 83 void solve() 84 { 85     int ans = 0; 86     int low = 0, high = m; 87     while(low <= high) 88     { 89         int mid = (low + high) >> 1; 90         build(mid); 91         if(check(n * 2)) ans = max(ans, mid), low = mid + 1; 92         else high = mid - 1; 93     } 94     printf("%d\n", ans); 95 } 96 int main() 97 { 98     while(scanf("%d%d", &n, &m) != EOF) 99     {100         if(n == 0 && m == 0) break;101         for(int i = 1; i <= n; i++)102         {103             scanf("%d%d", &a[i], &b[i]);104             a[i]++; b[i]++;105         }106         for(int i = 1; i <= m; i++)107         {108             scanf("%d%d", &x[i], &y[i]);109             x[i]++; y[i]++;110         }111         solve();112     }113     return 0;114 }