本文共 1113 字，大约阅读时间需要 3 分钟。

  【关键是将题目中的n+m条边作为点，在有公共点的两边(转化后是两点)之间连一条边】

#include
   
    #include
    
     #define N 2005struct edge{     int to,next;}e[N*100];int n,o,m,ans,t;int head[N];bool v[N];int map[105][105];void add(int x,int y){  // printf("!!!!!!!!%d %d\n",x,y);    e[o].to=y;    e[o].next=head[x];    head[x]=o++;    e[o].to=x;    e[o].next=head[y];    head[y]=o++;}void dfs(int now){    v[now]=1;t++;    for (int k=head[now];k!=-1;k=e[k].next)        if (!v[e[k].to])dfs(e[k].to);}void doit(){   int x,y;    o=0;memset(head,255,sizeof(head));    memset(map,0,sizeof(map));    ans=0;    for (int i=1;i<=n;i++)        {scanf("%d%d",&x,&y);         map[x][y]=i;         map[x+1][y]=i;        }    for (int i=1;i<=m;i++)        {scanf("%d%d",&x,&y);         if (map[x][y]) add(map[x][y],n+i);         if (map[x][y+1]) add(map[x][y+1],n+i);        }    memset(v,0,sizeof(v));    for (int i=1;i<=n+m;i++)        if (!v[i])           {               t=0; dfs(i); ans+=(t+1)/2;           }    printf("%d\n",ans);}int main(){   while (scanf("%d%d",&n,&m),n||m) doit();    return 0;}
    
   

转载地址：https://blog.csdn.net/chm517/article/details/9499563 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！