#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;
int N;
vector<pii> pts;
vector<int> vert[200001],
hor[200001];
vector<int> edges[200001];
bitset<200001> vis;
int par[200001],
col[200001];
void dfs(int node, int clr){
if(vis[node]) return;
vis[node] = true;
col[node] = clr;
for(auto u : edges[node])
dfs(u, 1 -clr);
}
void color(){
for(int i=0; i<N; i++) col[i] = -1;
vis.reset();
for(int i=0; i<N; i++){
if(!vis[i]) dfs(i, 1);
}
}
bool find_path(int node){
if(vis[node]) return false;
vis[node] = true;
for(auto u : edges[node])
if(par[u] == -1){
par[u] = node;
return true;
}
for(auto u: edges[node])
if(find_path(par[u])){
par[u] = node;
return true;
}
return false;
}
int match(){
for(int i=0; i<=N; i++) par[i] = -1;
int num_match = 0;
for(int i=0; i<N; i++){
if(par[i] == -1 && col[i] == 1){
vis.reset();
if(find_path(i))
num_match ++;
}
}
return num_match;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
pts.resize(N);
for(int i=0; i<N; i++){
int a, b; cin >> a >> b;
vert[a].push_back(i),
hor[b].push_back(i);
pts[i] = mp(a, b);
}
for(int i=0; i<=N; i++){
if(vert[i].size() == 2)
edges[vert[i][0]].push_back(vert[i][1]),
edges[vert[i][1]].push_back(vert[i][0]);
if(hor[i].size() == 2)
edges[hor[i][0]].push_back(hor[i][1]),
edges[hor[i][1]].push_back(hor[i][0]);
}
color();
int M = match();
//cout << M << "\n";
if(M != N/2){
cout << "NE\n";
return 0;
}
cout << "DA\n";
for(int i=0; i<=N; i++) if(par[i] != -1) cout << i +1<< " " << par[i] +1<< "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
14328 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
14328 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
14328 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
14328 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
14328 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |