1 条题解

  • 0

    题意分析:

    给定一个N点M边的无向图,为每个边编号1~M,若点的入度>1,其相关边编号的最大公约数为1,有解则输出方案。

    解题思路:

    用DFS进行编号,将同一点的相关边存入向量组,依据gcd(x,x+1)=1gcd(x,x+1)=1,将其相关边顺序编号

    实现步骤

    输入:读取 n(顶点数)、m(边数)及所有边。 生成质数:用筛法生成前 m 个质数(如 [2, 3, 5, 7, ...])。 分配编号:将质数按输入顺序依次赋给每条边。 输出: 第一行输出 YES(必有解)。 第二行输出分配的质数列表。

    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <vector>
    #define maxn 52
    using namespace std;
    vector<int> a[maxn];
    int n,m,no;
    int f[maxn][maxn];
    int id[maxn*maxn];
    bool vis[maxn];
    void DFS(int u){
        vis[u]=1;
        int v;
        for(int i=0;i<a[u].size();i++){
            v=a[u][i];
            if(!vis[v]){
                id[f[u][v]]=++no;
                DFS(v);
            }
            else if(!id[f[u][v]]) id[f[u][v]]=++no;
        }
    }
    int main(){
        cin>>n>>m;
        no=0;
        memset(vis,0,sizeof(vis));
        memset(id,0,sizeof(id));
        int x,y;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            a[x].push_back(y);
            a[y].push_back(x);
            f[x][y]=f[y][x]=i;
        }
        for(int i=1;i<=n;i++)
            if(!vis[i]) DFS(i);
        printf("YES\n");
        for(int i=1;i<m;i++)
            printf("%d ",id[i]);
        printf("%d\n",id[m]);
        return 0;
    }
    
    • 1

    信息

    ID
    1344
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    5
    已通过
    2
    上传者