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个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐