首页 > 代码库 > Codeforces 405E DFS

Codeforces 405E DFS

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

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

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

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

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

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

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

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

#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <queue>using namespace std;const int N=100000+10;int u[N<<1],v[N<<1],nt[N<<1],ft[N];int n,m,cnt;int vis[N<<1];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!=-1;i=nt[i]){        int nx=v[i];        if (vis[i] || nx==f) continue;        vis[i]=vis[i^1]=1;        int r=dfs(nx,x);        if (r){            printf("%d %d %d\n",x,nx,r);        }        else{            vec.push(nx);        }    }    while (vec.size()>=2){        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 0;}int main(){    while (scanf("%d%d",&n,&m)!=EOF)    {        cnt=0;        memset(ft,-1,sizeof ft);        memset(vis,0,sizeof vis);        int a,b;        for (int i=0;i<m;i++){            scanf("%d%d",&a,&b);            add(a,b);            add(b,a);        }        //cout<<m<<" "<<(m&1)<<endl;        if (m&1){            puts("No solution");            continue;        }        dfs(1,-1);    }    return 0;}