Codeforces 405E DFS

这个题目要求把一个无向连通图里面的所有边，分成两个一对，只能出现一次，而且一对边必须是连在一起的，点可以复用但边不可复用

可解条件很易得，因为图是连通的，只要边数为偶数即可。

一开始我借着做欧拉回路的方法，直接DFS暴搜，沿路做标记，遇到未标记的连续两条边输出即可

不过事实证明这个算法是错的

暴搜能成立只是建立在图上的边可以存在很多个边对里，但肯定有图不满足这种条件

其实解决方法也就是在DFS的基础上对特殊边进行下考虑即可

即每次对某个点，对子节点进行dfs，如果发现子节点下面有落单的边，则将当前边和子节点的落单边组合起来输出

否则就把当前边存进该点独有的队列中，全部存完后，两两进行输出，如果有落单边，给父亲返回，告诉他这里有落单边即可。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

const int N=+;

int u[N<<],v[N<<],nt[N<<],ft[N];

int n,m,cnt;

int vis[N<<];

void add(int a,int b)

{

    u[cnt]=a;

    v[cnt]=b;

    nt[cnt]=ft[a];

    ft[a]=cnt++;

}

int dfs(int x,int f)

{

    queue<int> vec;

    for (int i=ft[x];i!=-;i=nt[i]){

        int nx=v[i];

        if (vis[i] || nx==f) continue;

        vis[i]=vis[i^]=;

        int r=dfs(nx,x);

        if (r){

            printf("%d %d %d\n",x,nx,r);

        }

        else{

            vec.push(nx);

        }

    }

    while (vec.size()>=){

        int a=vec.front();

        vec.pop();

        int b=vec.front();

        vec.pop();

        printf("%d %d %d\n",a,x,b);

    }

    if (!vec.empty()){

        int a=vec.front();

        vec.pop();

        return  a;

    }

    return ;

}

int main()

{

    while (scanf("%d%d",&n,&m)!=EOF)

    {

        cnt=;

        memset(ft,-,sizeof ft);

        memset(vis,,sizeof vis);

        int a,b;

        for (int i=;i<m;i++){

            scanf("%d%d",&a,&b);

            add(a,b);

            add(b,a);

        }

        //cout<<m<<" "<<(m&1)<<endl;

        if (m&){

            puts("No solution");

            continue;

        }

        dfs(,-);

    }

    return ;

}

巴特西

Codeforces 405E DFS

最新文章

热门文章