| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 7295 | Accepted: 2778 |
Description
Behind the large door, there is a nesting *, which consists of M floors. Each floor except the deepest one has a door leading to the next floor, and there are two locks in each of these doors. Ratish can pass through a door if he opens either of the two locks in it. There are 2N different types of locks in all. The same type of locks may appear in different doors, and a door may have two locks of the same type. There is only one key that can unlock one type of lock, so there are 2N keys for all the 2N types of locks. These 2N keys were divided into N pairs, and once one key in a pair is used, the other key will disappear and never show up again.
Later, Ratish found N pairs of keys under the rock and a piece of paper recording exactly what kinds of locks are in the M doors. But Ratish doesn't know which floor Luffy is held, so he has to open as many doors as possible. Can you help him to choose N keys to open the maximum number of doors?
Input
Output
Sample Input
3 6
0 3
1 2
4 5
0 1
0 2
4 1
4 2
3 5
2 2
0 0
Sample Output
4
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector> using namespace std; const int MAX_N = ( << ) + ;
int N,M;
int low[MAX_N],pre[MAX_N],cmp[MAX_N];
int dfs_clock,scc_cnt;
stack <int > S;
int no[MAX_N],x[],y[];
vector<int> G[MAX_N]; void dfs(int u) {
pre[u] = low[u] = ++dfs_clock;
S.push(u);
for(int i = ; i < G[u].size(); ++i) {
int v = G[u][i];
if(!pre[v]) {
dfs(v);
low[u] = min(low[u],low[v]);
} else if(!cmp[v]) {
low[u] = min(low[u],pre[v]);
}
} if(low[u] == pre[u]) {
++scc_cnt;
for(;;) {
int x = S.top(); S.pop();
cmp[x] = scc_cnt;
if(x == u) break;
}
}
}
void scc() {
dfs_clock = scc_cnt = ;
memset(cmp,,sizeof(cmp));
memset(pre,,sizeof(pre)); for(int i = ; i < * N; ++i) {
if(!pre[i]) dfs(i);
}
}
bool check(int m) {
for(int i = ; i < * N; ++i) {
G[i].clear();
}
for(int i = ; i <= m; ++i) {
int a = x[i],b = y[i];
G[no[a]].push_back(b);
G[no[b]].push_back(a);
}
scc();
for(int i = ; i < * N; ++i) {
if(cmp[i] == ) continue;
if(cmp[i] == cmp[ no[i] ]) {
//printf("i = %d no = %d %d %d\n",i,no[i],cmp[i],cmp[no[i]]);
return false;
}
} return true;
}
void solve() {
int l = ,r = M;
while(l < r) {
int mid = (l + r + ) / ;
if(check(mid)) l = mid;
else r = mid - ;
}
printf("%d\n",l);
}
int main()
{
//freopen("sw.in","r",stdin);
while(~scanf("%d%d",&N,&M)) {
if(N == && M == ) break;
for(int i = ; i <= N; ++i) {
int a,b;
scanf("%d%d",&a,&b);
no[a] = b;
no[b] = a;
}
for(int i = ; i <= M; ++i) {
scanf("%d%d",&x[i],&y[i]);
} solve(); }
return ;
}