题意大致是将图中的点划分为两部分,就是求问二分图,输出划分成二分图的两部分分别是什么。
数据量稍微大一点,使用邻接表或者链式前向星存储。
算法实现过程大概如下划分:
- 实现前向星存储
- 二分图染色判定
- 结果输出
存储和输出没什么问题,输出也没有固定要求,答案不唯一,在判定的过程中有如下坑点:
图可能不是连通图,有的点连不上,因此不能仅从某一个点出发做一次DFS,要从每个点都出发。
第一个数据虽然存在4这一个孤立点,但是从1出发依然能得到一个符合题意的答案,所以第一个数据检验不出这个坑点
正确写法如下:
#include <iostream>
#include <cstdio>
using namespace std;
typedef struct node {
int u;
int v;
int w;
int next;
}edge;
edge e[1000000];
int n, m;
int head[1000010];
int num;
int color[1000010];
void init() {
num = 0;
for (int i = 0; i <= 1000000; i++) {
head[i] = -1;
}
}
void addedge(int u, int v) {
e[num].v=v;
e[num].w=0;
e[num].next = head[u];
head[u] = num++;
// cout << u << num << endl;
}
bool DFS(int u) {
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(color[v]==color[u]) return false;
if(!color[v]) {
color[v]=3-color[u];
if(!DFS(v)) return false;
}
}
return true;
}
int main() {
init();
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
addedge(u, v);
addedge(v, u);
}
// for (int i = 1; i <= n; i ++) {
// for (int j = head[i]; j != -1; j = e[j].next) {
// cout << i << " " << e[j].v << endl;
// }
// }
for (int i = 1; i <= n; i++) {
if(color[i] != 0) continue; //是否染过色,能减少计算量
if(head[i] == -1) { //如果是孤立点,不与其他点联通,随便染一个0 1 2 都行
color[i] = 1;
continue;
}
color[i] = 1;
if(!DFS(i)) {
cout << "-1" << endl;
return 0;
}
}
int white = 0;
int black = 0;
for (int i = 1; i <= n; i++) {
//cout << color[i] << endl;
if(color[i] == 1) white ++;
if(color[i] == 2) black ++;
}
cout << white << endl;
for (int i = 1; i <= n; i++) {
if(color[i] ==1) cout << i << " ";
}cout << endl;
cout << black << endl;
for (int i = 1; i <= n; i++) {
if(color[i] ==2) cout << i << " ";
}cout << endl;
return 0;
}