视屏网站开发者工具无视频文件,网站流量统计系统企业版,潍坊学网站建设,dz门户做视频网站题意#xff1a;
有 n 个点和 m 条边#xff0c;对点进行染色。要求一条边的两个点不能都染色#xff0c;并且删除两端都没有染色的边之后#xff0c;图连通。请给出一种染色方案。
题解#xff1a;
第一反应就是01染色#xff0c;但是题目是有可能存在奇环的#xf…题意
有 n 个点和 m 条边对点进行染色。要求一条边的两个点不能都染色并且删除两端都没有染色的边之后图连通。请给出一种染色方案。
题解
第一反应就是01染色但是题目是有可能存在奇环的那怎么办 01染色是保证1和1,0和0都不能相邻如果把1当做染色根据本题0是可以相邻的那我们把01染色的dfs改成bfs的形式也就是与1相邻的点都是0然后对于每个0所能到的下一个点就是1然后对1操作1的周围都是0这样循环进行就可以 BFS遍历所有的点。
如果当前节点没有染色且相邻的所有节点没有染色就染色否则不染色。如果当前节点已经染色那么把相邻的所有节点标记不染色。 证明显然这种方案不会存在一条边的两端都染色的情况并且如果图不连通一定是有一个点连接的所有点都不染色而这样的点一定会在第一种情况下被染色所以图一定是连通的。 当然如果图本身就不连通直接输出NO u1s1div2的F题比我想象的要简单多
代码
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includeiostream
#includealgorithm
#includestring.h
#includevector
#includequeue
#includemap
using namespace std;
#define LL long long
#define eps (1e-8)
const int maxn 3e5 10;
const int inf 0x3f3f3f3f;
const LL mod 1e9 7;
struct node
{int v, nxt;
}e[maxn 1];
int head[maxn], cnt;
void add(int u, int v)
{e[cnt].v v;e[cnt].nxt head[u];head[u] cnt;
}
int vis[maxn];//标记为1是染色0位不染色-1位还未遍历的点
queueintq;
void bfs(int u)
{vis[u] 1;for (int i head[u]; i; i e[i].nxt){int v e[i].v;// if (vis[v] -1){vis[v] 0; q.push(v);//存的都是不染色的点}}
}
void solve()
{while (!q.empty()){int u q.front();q.pop();for (int i head[u]; i; i e[i].nxt){int v e[i].v;//v为染色点 if (vis[v] -1){bfs(v);}}}
}
int main()
{int t;scanf(%d, t);while (t--){cnt 0;int n, m;scanf(%d%d, n, m);for (int i 0; i n; i){head[i] 0;vis[i] -1;}int u, v;while (m--){scanf(%d%d, u, v);add(u, v), add(v, u);}bfs(1);solve();int flag 1, ans 0;for (int i 1; i n; i){if (vis[i] 1)ans;else if (vis[i] -1)//说明有的点没有遍历到图不连通 {flag 0;}}if (flag){printf(YES\n);printf(%d\n, ans);for (int i 1; i n; i){if (vis[i] 1)printf(%d , i);}printf(\n);}else{printf(NO\n);}}return 0;
}
