*Codeforces Round #766 (Div. 2) C. Not Assigning（dfs）

本文主要是介绍*Codeforces Round #766 (Div. 2) C. Not Assigning（dfs），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://codeforces.com/contest/1627/problem/C

给你一个n个顶点的树，顶点从1到n，边从1到n-1。树是没有圈的连通无向图。你必须给树的每条边分配整数权重，这样得到的图就是一个素数树。

素数树是指由一条或两条边组成的每条路的重量都是素数的树。一条路径不应该访问任何顶点两次。路径的权重是该路径上的边权重之和。

输出
对于每个测试案例，如果存在有效的赋值，则打印包含n-1个整数a1、a2、…、a[n-1](1≤ai≤10^5)的单行，其中ai表示分配给编号为I的边的权重，否则打印-1。

input
3
2
1 2
4
1 3
4 3
2 1
7
1 2
1 3
3 4
3 5
6 2
7 2
output
17
2 5 11
-1

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=200200;
int h[N],e[N],ne[N],idx;
int n,nums[N],res[N];
bool st[N];
map<PII,int> mp;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x,int nn)//节点名称，命名数值
{
    st[x]=1;//表示已经命名过了
    for(int i=h[x];i!=-1;i=ne[i])//扫一遍子节点
    {
        if(!st[e[i]])//没有走过的话就可以命名一下
        {
            mp[{x,e[i]}]=nn;//定义数值
            dfs(e[i],5-nn);//往下子节点继续3 2 3 2定义
        }
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)
    {
        memset(h,-1,sizeof h);//初始时所有指针指向自己，都是单独的点
        memset(nums,0,sizeof nums);//所有点能连接的都一条边都没有
        memset(st,0,sizeof st);//都没有走过
        mp.clear();

        vector<PII> v;
        bool flag=true;
        
        cin>>n;
        for(int i=1;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            add(a,b);//建边
            add(b,a);
            v.push_back({a,b});//插入边
            v.push_back({b,a});
            nums[a]++;//这个节点所带的边数
            nums[b]++;
            if(nums[a]>=3||nums[b]>=3) flag=false;
        }
        if(flag==false) cout<<"-1"<<endl;
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(nums[i]==1)
                {
                    dfs(i,2);//第一个节点定义为2
                    break;
                }
            }
            for(int i=0;i<v.size();i++)
            {
                //只有非0的时候，才可以输出数值
                if(mp[v[i]]) cout<<mp[v[i]]<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}

这篇关于*Codeforces Round #766 (Div. 2) C. Not Assigning（dfs）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！