作法：
首先考慮一個會有問題的作法：對於每個點，往他上下左右四個方向最近的點分別連一條邊（如果沒有點就不用連），然後直接對這張圖二塗色。而這樣隨便都能構一個出現奇環的測資讓他爛掉，因此我們可以考慮先把圈都拔光，具體來說，我們考慮一種比較特別的圈，如果沿著這樣的圈一直走的話，走的方向依序是「橫直橫直......」，也就是每走一個點都會轉$90$度。顯然這樣的圈的點數為偶數，那麼沿著這個圈一路途上紅藍交錯的顏色，就可以把這個圈上的所有點砍掉了，因為塗完後他讓每條鉛直線和水平線上的紅藍點數增加的個數相同。因此只要把這種圈都砍完之後，剩下的圖就可以用剛才提到的那個演算法了：直接把圖建出來二塗色，因為此時已經沒有圈了（容易證明，當不存在剛才那種「特別的圈」時，原本的圖裡也不會有圈），所以直接塗就可以了。
所以重點在於要如何找圈然後把他拔掉，首先考慮直接DFS的算法，也就是走到一個點的時候，考慮所有和他同行（或同列，只會是其中一個，因為我們要找的是剛才提到的特別的圈）的點DFS下去，當找到一條回邊，也就是形成了一個圈時，就沿著父親一直走上去，並沿路塗色，塗完後直接中斷這次的DFS，一直 return 回去直到當前的點的答案還沒被決定為止，然後之後在DFS的時候就可以完全無視那些已經被塗過色的點了。這個算法還有需要注意的地方，因為當我們最一開始DFS的時候一定是先選一個方向去DFS，也就是假設從這個點出發是先走橫的，這樣之後DFS的過程就知道現在這個點的下一步是走橫的還是直的。而如果結束DFS的時候根節點還沒有被塗色，就要去DFS起點是走直的的情況，否則之後在以其他點當根DFS的時候，當戳到了這個還沒被塗色的舊根節點時會誤以為這是一條回邊，這時沿著父親走就會爛掉。
顯然這個算法複雜度會爛掉，於是我只好用 linked list 優化 DFS ，這東西在TIOJ 1220也有用到類似的東西（雖然我當時的解不是那樣做的），具體來說就是：對每個$x$座標維護一條 linked list ，代表當前的$x$座標等於他的點中還剩下這些點。對每個$y$座標一樣也有一條 linked list 。由這裡可以看出每個原圖中的點$P$會對應到兩個在 linked list 中的節點$nx,ny$（其中$nx$是被放在「$x$座標的lonked list」中的節點，$ny$則是$y$座標的），並且讓$nx$代表走到$P$時下一步是要走鉛直方向的，$ny$則是代表走到$P$時下一步是要走水平方向的。
建好 linked list 後就可以DFS了，當走到一個點$P$時，假設他現在要走的是直的方向，那麼就先把他對應的$nx$拔掉，然後去他的$x$座標這條 linked list 裡找後繼節點，當找到一個後繼節點$Q$時就直接把$Q$對應的$nx$拔掉再DFS下去，一樣當找到一個圈的時候就一樣沿路塗色並一直 return 。但這樣做會有問題，會發現根本找不到圈，因為當一個點被走到時他所對應的$nx,ny$都已經被拔掉了，之後當然就不會有任何邊走向他了。解決方法是當在DFS時，假設現在是$P$找到了他的後繼節點$Q$（和剛剛一樣），那麼在DFS下去之前先不要把$Q$的$nx$拔掉，等到DFS出來之後再拔掉，因為如果有圈形成的話他的回邊一定是連向$Q$的$nx$的。最後還要注意到剛才用 linked list 優化之前的那個細節，也就是根節點要記得擴展完，因此當最一開始DFS進去是選$x$方向的 linked list 的話，出來之後發現根節點還沒被塗色，就要試試看選$y$方向的。
code :
#include<bits/stdc++.h> using namespace std; const int maxn=200000+10 ; struct P{int x,y,id;}; bool cmp1(const P &a,const P &b) { return a.x==b.x ? a.y<b.y : a.x<b.x ; } bool cmp2(const P &a,const P &b) { return a.y==b.y ? a.x<b.x : a.y<b.y ; } P p[maxn] ; struct node { node *las,*nex ; int id ; node(int _id){las=nex=NULL ; id=_id ;} }*head[3][maxn] , *nd[3][maxn] ; void add_node(int type,int x,int id) { node *u=head[type][x] ; head[type][x]=new node(id) ; head[type][x]->nex=u ; if(u) u->las=head[type][x] ; } void erase(int type,int id,node *u) { if(u==head[type][id]) head[type][id]=u->nex ; else { u->las->nex=u->nex ; if(u->nex) u->nex->las=u->las ; } } bool vis[maxn] ; int fa[maxn],ans[maxn] ; void dfs(int x,int f,int type) { vis[x]=1 ; fa[x]=f ; int id=(type==1 ? p[x].x : p[x].y) ; erase(type,id,nd[type][x]) ; for(node *u=head[type][id];u;u=head[type][id]) { if(vis[u->id]) { for(int i=x,col=type^3;;i=fa[i],col^=3) { ans[i]=col ; int id2=(col==1 ? p[i].x : p[i].y) ; erase(col,id2,nd[col][i]) ; if(i==u->id) break ; } return ; } else { dfs(u->id,x,type^3) ; head[type][id]=u->nex ; if(ans[x]) return ; } } } vector<int> v[maxn] ; void build_graph(int n) { sort(p+1,p+n+1,cmp1) ; for(int i=1;i<n;i++) if(p[i].x==p[i+1].x) v[p[i].id].push_back(p[i+1].id) , v[p[i+1].id].push_back(p[i].id) ; sort(p+1,p+n+1,cmp2) ; for(int i=1;i<n;i++) if(p[i].y==p[i+1].y) v[p[i].id].push_back(p[i+1].id) , v[p[i+1].id].push_back(p[i].id) ; } void dfs2(int x,int f=-1,int c=1) { ans[x]=c ; for(auto i : v[x]) if(i!=f) dfs2(i,x,3-c) ; } main() { if(fopen("in","r")) freopen("in","r",stdin) ; int n ; scanf("%d",&n) ; for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y) ; p[i].id=i ; add_node(1,p[i].x,i) ; add_node(2,p[i].y,i) ; nd[1][i]=head[1][p[i].x] ; nd[2][i]=head[2][p[i].y] ; } for(int i=1;i<=n;i++) if(!vis[i]) { dfs(i,-1,1) ; if(!head[2][p[i].y] || ans[i]) continue ; if(!head[2][p[i].y]->nex) continue ; dfs(i,-1,2) ; } int n2=0 ; for(int i=1;i<=n;i++) if(!ans[i]) p[++n2]=p[i] ; build_graph(n2) ; memset(vis,0,sizeof(vis)) ; for(int i=1;i<=n;i++) if(!ans[i]) dfs2(i) ; for(int i=1;i<=n;i++) printf("%c",ans[i]==1?'b':'r') ; printf("\n") ; }
沒有留言:
張貼留言