#include <bits/stdc++.h>
int N, K;
int stk[4000010][2];
int chk[2010][2010];
int xx[]={0,0,1,-1}, yy[]={1,-1,0,0};
struct Union_Find
{
std::vector<int> parent, rank;
Union_Find() { for(int i=0; i<100010; i++) parent.push_back(i), rank.push_back(1);}
int find(int u) { return u==parent[u]?u:parent[u]=find(parent[u]);}
int merge(int u, int v) {
u=find(u), v=find(v);
if(u==v)return 0;
if(rank[u]>rank[v]) std::swap(u,v);
parent[u]=v;
if(rank[u]==rank[v]) ++rank[v];
return 1;
}
};
int check(int x, int y)
{
if (!x||!y||x>N||y>N) return 1;
return 0;
}
int main()
{
scanf("%d %d", &N, &K);
Union_Find civilization;
int i, j, x, y;
int top=0;
for (i=0; i<K; i++) {
scanf("%d %d", &x, &y);
chk[x][y]=i+1;
stk[top][0]=x, stk[top++][1]=y;
}
int fr, re;
fr=0, re=top;
int cnt=K, k=0, l;
for(i=0; i<re; i++) {
for (j=0; j<4; j++) {
if (checK(stk[i][0]+xx[j],stk[i][1]+yy[j])) continue;
if (chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]]) cnt-=civilization.merge(chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]],chk[stk[i][0]][stk[i][1]]);
}
}
if (cnt==1) {printf("0"); return 0;}
while(fr<re) {
k++;
for (i=fr; i<re; i++) {
for (j=0; j<4; j++) {
if (check(stk[i][0]+xx[j],stk[i][1]+yy[j])) continue;
if (chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]]) {
cnt-=civilization.merge(chk[stk[i][0]][stk[i][1]], chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]]);
}
else {
chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]]=chk[stk[i][0]][stk[i][1]];
stk[top][0]=stk[i][0]+xx[j], stk[top][1]=stk[i][1]+yy[j];
for (l=0; l<4; l++) {
if (check(stk[top][0]+xx[l],stk[top][1]+yy[l])) continue;
if (chk[stk[top][0]+xx[l]][stk[top][1]+yy[l]]) {
cnt-=civilization.merge(chk[stk[top][0]][stk[top][1]], chk[stk[top][0]+xx[l]][stk[top][1]+yy[l]]);
}
}
top++;
}
}
}
if (cnt==1) {
printf("%d", k);
return 0;
}
fr=re; re=top;
}
return 0;
}
Compilation message
civilization.cpp: In function 'int main()':
civilization.cpp:41:8: error: 'checK' was not declared in this scope
if (checK(stk[i][0]+xx[j],stk[i][1]+yy[j])) continue;
^~~~~
civilization.cpp:41:8: note: suggested alternative: 'check'
if (checK(stk[i][0]+xx[j],stk[i][1]+yy[j])) continue;
^~~~~
check
civilization.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &K);
~~~~~^~~~~~~~~~~~~~~~~
civilization.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
