xiaonanan哈密顿回路篇

杭电 3018
father[fa]=fb,写成father[a]=fb;
难受，是真的难受
弄错了，搞了我几个小时，还是对并查集不熟悉 呀，时刻告诫自己心态不要崩。
考察点： 一笔画 问题 对于 全是偶度点的连通图可以 一笔画
对于 存在N个奇度点的连通图可以 画 N/2 笔

孤立点不算

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
int father[100005],du[100005];
int ji[100005];
bool vis[100005];
//寻找父亲节点
int findf(int x)
{
    if(x!=father[x])
    {
        father[x]=findf(father[x]);
    }
    return father[x];
}
int main()
{
    int n,m,fa,fb,i;
    int ans=0;
    int a,b;
    int fat;
    vector<int>ff;
    int vv;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
       ff.clear();
       ans=0;
       for(i=1;i<=n;i++)
       {
         vis[i]=false;
         du[i]=0;
         ji[i]=0;
         father[i]=i;
       }
       for(i=0;i<m;i++)
       {
           scanf("%d%d",&a,&b);
           du[a]++;
           du[b]++;
           fa=findf(a);
           fb=findf(b);
           if(fa!=fb)
           {
            father[fa]=fb;
           }
       }

       for(i=1;i<=n;i++)
       {
         fat=findf(i);
        if(!vis[fat])
        {
            vis[fat]=true;
            ff.push_back(fat);
        }
        if(du[i]&1)
        {
           ji[fat]++;
        }
       }
       for(i=0;i<ff.size();i++)
       { vv=ff[i];
           if(du[vv]==0)
            continue;
            if(ji[vv]==0)
            ans++;
           else
           {
              ans+=(ji[vv]/2);
           }
       }
       printf("%d\n",ans);
    }
    return 0;
}

杭电 3018
一个无向图 每个点至少与其他一半的点存在边，我刚开始没有判断没有哈密顿回路的情况，也是对的，应该题目的情况肯定存在哈密顿回路吧。

#include<bits/stdc++.h>
using namespace std;
int mapp[151][151];
bool vis[151];
int rd[151];
int n,m;
int cnt=0;
bool flag=false;
void dfs(int x,int num)
{
    rd[num]=x;
    vis[x]=true;
    if(num==(n))
    {
        if(mapp[1][x])
        flag=true;
        return;
    }
    for(int i=1;!flag&&i<=n;i++)
    {
        if(mapp[x][i]&&!vis[i]&&!flag)
        {
            dfs(i,num+1);
            vis[i]=false;
        }
    }
    return;
}
int main()
{
   while(~scanf("%d%d",&n,&m))
   {
       cnt=0;
       memset(mapp,0,sizeof(mapp));
       memset(vis,false,sizeof(vis));
       flag=false;
       for(int i=0;i<m;i++)
       {
           int a,b;
           scanf("%d%d",&a,&b);
           mapp[a][b]=1;
           mapp[b][a]=1;
       }
       dfs(1,1);
       if(flag)
       {
           for(int i=1;i<n;i++)
           {
               printf("%d ",rd[i]);
           }
            printf("%d\n",rd[n]);
       }
       else
       {
           printf("no solution\n");
       }
   }
    return 0;
}