题目链接：https://www.nowcoder.com/acm/contest/106#question
C题 Professional Manager
#include <bits/stdc++.h> using namespace std; int root[200005],siz[200005],last[200005]; int n,q,u,v; int get(int i) { if(root[i]!=i) return get(root[i]); return root[i]; } void ops1() { scanf("%d%d",&u,&v); u=get(last[u]),v=get(last[v]); if(u==v) return; root[u]=v; siz[v]+=siz[u]; } void ops2() { scanf("%d",&u); siz[get(last[u])]--; siz[++n]=1; last[u]=root[n]=n; } void ops3() { scanf("%d",&u); printf("%d ",siz[get(last[u])]); } void ops4() { scanf("%d%d",&u,&v); if(get(last[u])==get(last[v])) printf("YES "); else printf("NO "); } int main() { int t; scanf("%d",&t); for(int j=1;j<=t;j++) { printf("Case #%d: ",j); scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) last[i]=i,root[i]=i,siz[i]=1; while(q--) { int m; scanf("%d",&m); switch(m) { case 1: ops1();break; case 2: ops2();break; case 3: ops3();break; case 4: ops4();break; } } } return 0; } /* /// 用last记录当前元素的前位 /// 查询当前元素根 则 查询当前元素的last的根 ///// 当要从集合中去掉某元素时 ///// 改变其last root[last]=last siz[last]=1 /// 这样不会影响到在其下的其他元素查询根的过程 当合并了2 3,3 4,4 5 last 3 4 5 5 | | | | root 2-3-4-5 siz 1 2 3 4 此时若去掉3 last 3 6 5 5 | | | | root 2-3-4-5 siz 1 1 3 3 */
L题 Fresh Air
#include <algorithm> #include <string.h> #include <cstring> #include <stdio.h> #include <queue> using namespace std; struct NODE{int x,y;}a[100005]; //supercalifragilisticexpialidocious area被树围住 从外部无法到达 //cnt为无法到达的区域大小 无法到达的区域设为0 int n,cnt,G[2005][2005],ans[100005]; int mov[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; bool bound(int x,int y) { return x<0||x>2000||y<0||y>2000; } void bfs(int x,int y) { /// bfs过程中 遇到1就停止 /// 能从该点出发而到达的0都变为2 无法到达的0则不变 queue <NODE> q; q.push((NODE){x,y}); G[x][y]=2; cnt--; while(!q.empty()) { NODE tmp=q.front(); q.pop(); for(int i=0;i<4;i++) { int nowx=tmp.x+mov[i][0], nowy=tmp.y+mov[i][1]; if(bound(nowx,nowy)) continue;//越界 if(G[nowx][nowy]) continue;//能到达或已访问过 G[nowx][nowy]=2; cnt--; //该点为能够到达的0 cnt--即去掉该点 q.push((NODE){nowx,nowy}); } } } bool check(int x,int y) { for(int i=0;i<4;i++) { // 若存在因该点的树而停止继续搜索的情况 int nowx=x+mov[i][0], nowy=y+mov[i][1]; if(bound(nowx,nowy)) continue;//越界 if(G[nowx][nowy]==2) return 1; ///即该点四周有bfs时被变为2的点 } return 0; } int main () { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].x+=1000, a[i].y+=1000; G[a[i].x][a[i].y]=1; } cnt=2001*2001-n; bfs(0,0);//先bfs一遍 ///此时res等于减去1和2后余下的无法到达的0的个数 for(int i=n;i>0;i--) //从最后一点向前遍历 { ans[i]=cnt++; G[a[i].x][a[i].y]=0; ///删除该点放置的树 if(check(a[i].x,a[i].y)) bfs(a[i].x,a[i].y); //从该点继续bfs } for(int i=1;i<=n;i++) printf("%d ",ans[i]); } return 0; }