编程介的小学生 2018-12-11 06:45 采纳率: 19%
浏览 384
已采纳

C语言求问这个二进制转换的问题怎么计算,要用到图的知识

Problem Description
soda has a undirected graph with n vertices and m edges. He wants to make the graph become a bipartite graph by deleting only one vertex. You need to tell him which vertex can be deleted.

Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first contains two integer n and m (1≤n,m≤105), the number of vertices and the number of edges.
Next m lines contain two integers each, ui and vi (1≤ui,vi≤n,ui≠vi) , indicating there is an edge between vertices ui and vi.

Output
For each test case, output binary string of length n. The i-th character is '1' if soda can delete i-th vertex to make the graph become a bipartite graph, otherwise the i-th character is '0'.

Sample Input
2
5 4
1 4
2 4
3 5
4 5
5 5
1 2
1 3
2 3
2 4
3 5

Sample Output
11111
11100

  • 写回答

1条回答

      报告相同问题?

      相关推荐 更多相似问题

      悬赏问题

      • ¥15 unity 使用 Vuforia 导入Model target 成功后database下拉菜单不显示导入的内容
      • ¥15 VBA跨工作簿获取目标工作簿内已有数据的列号
      • ¥30 Dijkstra‘s 最短路径
      • ¥15 在线教育培训平台,主要以点播视频和在线练习测试为主,除将视频做切片外,有其他哪种方式降低流量?(关键词-带宽速率)
      • ¥20 用c语音或c++实现银行叫号系统
      • ¥15 人工智能 规则正向演绎和推理
      • ¥20 基于STM32F401的电子密码锁设计
      • ¥15 famamacbeth回归中遇到only size-1 arrays can be converted to Python scalars,求解答
      • ¥15 单片机多个自锁按键的编程实践
      • ¥15 用python操作redis存储中文后,再取出的数据变成了乱码怎么办?