CF547D Mike and Fish 建图

题意：

分析：

　　其实也没什么好分析的，我这也是看的题解。

　　（不过，那篇题解好像文字的代码不太对劲）

　　这里直接说做法，正确性自证：

　　对输入的，将横、纵坐标相等的点分别两两连边，之后只需要dfs跑一个染色，使得一条边两个端点颜色都不一样即可，这样就可以确定每一个点放红色还是蓝色，输出即可。（至于哪个是红哪个是蓝不重要，有spj）

代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int N=;int n,m;

 struct node{int y,nxt;}e[*N];

 int h[N],c=,vis[N],ans[N][];

 void add(int x,int y){

     e[++c]=(node){y,h[x]};h[x]=c;

     e[++c]=(node){x,h[y]};h[y]=c;

 } void dfs(int x,int y){

     if(vis[x]) return ;vis[x]=y;

     for(int i=h[x];i;i=e[i].nxt)

     dfs(e[i].y,^y);

 } int main(){

     scanf("%d",&n);

     for(int i=,x,y;i<=n;i++){

         scanf("%d%d",&x,&y);

         if(ans[x][])

         add(ans[x][],i),ans[x][]=;

         else ans[x][]=i;

         if(ans[y][])

         add(ans[y][],i),ans[y][]=;

         else ans[y][]=i;

     } for(int i=;i<=n;i++){

         dfs(i,);

         if(vis[i]) putchar('r');

         else putchar('b');

     } return ;

 }

染色

巴特西

CF547D Mike and Fish 建图

题意：

分析：

最新文章

热门文章