1 条题解
-
0
题意分析:
给定一个N点M边的无向图,为每个边编号1~M,若点的入度>1,其相关边编号的最大公约数为1,有解则输出方案。
解题思路:
用DFS进行编号,将同一点的相关边存入向量组,依据,将其相关边顺序编号
实现步骤
输入:读取 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
- 上传者