#include <iostream> #include <vector> using namespace std; bool dfs(vector<vector<int>>& g, int v, int c, int* col) { col[v] = c; for (int i = 0; i < int(g[v].size()); ++i) { if (col[g[v][i]] != -1) { if (col[g[v][i]] != ((c+1)%2)) { return false; } } else { if (!dfs(g, g[v][i], ((c+1)%2), col)) { return false; } } } return true; } int main() { int n; cin >> n; vector<vector<int>> g = vector<vector<int>>(); int* color = new int[n]; for (int i = 0; i < n; ++i) { color[i] = -1; g.push_back(vector<int>()); } for (int i = 0; i < n; ++i) { int temp; while (true) { cin >> temp; if (temp == 0) { break; } g[i].push_back(temp-1); g[temp-1].push_back(i); } } for (int i = 0; i < n; ++i) { if (color[i] == -1) { if (!dfs(g, i, 0, color)) { cout << -1; delete(color); return 0; } } } for (int i = 0; i < n; ++i) { cout << color[i]; } delete(color); return 0; }解释算法思路
时间: 2024-02-16 19:27:48 浏览: 54
这是一个使用深度优先搜索(DFS)算法来判断一个无向图是否是二分图的程序。所谓二分图,是指能够将图中的所有节点分成两个不相交的子集,使得同一个子集内的节点没有边相连。程序中使用了一个一维数组 col 来记录每个节点的颜色,初始化为 -1。在 DFS 的过程中,每次遍历到一个相邻节点时,如果该节点已经被染色,需要判断颜色是否与当前节点的颜色相反,如果相同,则说明该无向图不是二分图;否则继续遍历。如果该节点还没有被染色,就将其染上与当前节点不同的颜色,然后递归遍历该节点。最后,如果所有节点都被遍历过,并且没有发现不合法的边,那么该无向图就是一个二分图。如果有不合法的边,就输出 -1 表示不是二分图。程序在读入无向图时,将每个节点的相邻节点存储在一个 vector 中,最后遍历每个节点,如果该节点还没有被染色,就从该节点开始进行 DFS。程序输出的是每个节点的颜色,0 或 1。
相关问题
#include <iostream>#include <vector>#include <stack>using namespace std;void dfs(int u, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& farthest) { stack<int> s; s.push(u); visited[u] = true; while (!s.empty()) { int v = s.top(); s.pop(); for (int i = 0; i < graph[v].size(); i++) { int w = graph[v][i]; if (!visited[w]) { visited[w] = true; s.push(w); farthest[w] = farthest[v] + 1; } } }}int main() { int n, m; cin >> n >> m; vector<vector<int>> graph(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u].push_back(v); } vector<int> farthest(n, 0); for (int i = 0; i < n; i++) { vector<bool> visited(n, false); dfs(i, graph, visited, farthest); } for (int i = 0; i < n; i++) { cout << "Node " << i << " can reach farthest node " << farthest[i] << endl; } return 0;}不用STL实现这个代码
不使用STL实现该代码,可以手动实现栈和vector。
下面是C++实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 10005;
int stack[MAXN], top = -1;
void push(int x) {
stack[++top] = x;
}
int pop() {
return stack[top--];
}
bool empty() {
return top == -1;
}
void dfs(int u, int graph[][MAXN], bool visited[], int farthest[]) {
push(u);
visited[u] = true;
while (!empty()) {
int v = pop();
for (int i = 0; i < MAXN; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = true;
push(i);
farthest[i] = farthest[v] + 1;
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
int graph[MAXN][MAXN] = {0};
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u][v] = 1;
}
int farthest[MAXN] = {0};
for (int i = 0; i < n; i++) {
bool visited[MAXN] = {false};
dfs(i, graph, visited, farthest);
}
for (int i = 0; i < n; i++) {
cout << "Node " << i << " can reach farthest node " << farthest[i] << endl;
}
return 0;
}
```
在这个实现中,我们手动实现了栈,并使用数组来代替vector。同时,我们使用二维数组来表示邻接矩阵,而不是vector<vector<int>>来表示邻接表。
其他部分的实现与使用STL的版本相同。
改进以下代码#include <iostream> #include <cstring> #include <algorithm> #include <set> #include <vector> using namespace std; const int maxn = 1010; set<int> Adj[maxn]; bool hs[maxn]; vector<int> path; int Nv,Ne,st; void Read() { cin >> Nv >> Ne >> st; for(int i=0;i<Ne;++i) { int u,v; cin >> u >> v; Adj[u].insert(v); Adj[v].insert(u); } } void dfs(int u) { hs[u] = 1; cout << u << ' '; for(auto v:Adj[u]) if(hs[v]==0) { path.push_back(v); //将这个节点加到path中 dfs(v); //递归 path.pop_back(); //递归完成以后,需要返回,这时就需要打印 // 返回时结点的信息,先删除尾元素,再打印 if(path.size()) //要判断path是否为空 cout << path.back() << ' '; } } int main() { Read(); dfs(st); int cnt=0; for(int i=1;i<=Nv;++i) cnt += hs[i]; //判断地图是否连通 cout << st ; if(cnt != Nv) puts(" 0"); return 0; }
这段代码是基于深度优先搜索(DFS)实现的地图遍历,对于小规模的地图遍历问题是可以使用的,但是若遇到大规模的地图遍历问题则会存在效率问题,因为该算法没有使用剪枝等优化方法,因此可能会出现重复遍历的情况。同时,该代码也没有进行错误处理,例如当输入的节点数或边数超过最大值时程序可能会崩溃。以下是对该代码的改进建议:
1. 使用邻接表存储图
该代码使用的是set存储图的节点,但是对于大规模的图来说,这种存储方式的效率并不高。可以使用邻接表来存储图,避免重复存储边信息,提高程序效率。
2. 使用剪枝优化
在DFS的过程中,可以使用剪枝来避免重复遍历相同的节点,提高程序效率。具体来说,可以使用一个布尔数组记录已经遍历过的节点,遇到已经遍历过的节点就跳过,避免重复遍历。
3. 添加错误处理
在读入节点数和边数时,应该进行错误处理,例如当输入的节点数或边数超过最大值时应该给出提示并退出程序。
4. 修改函数参数
在DFS函数中,应该将path参数传入函数中,而不是使用全局变量,这样可以避免在多线程环境下出现问题。
5. 简化代码逻辑
在DFS函数中,可以将打印节点信息的逻辑简化,避免使用额外的vector来记录遍历路径。可以在递归的过程中传递已遍历的节点信息,然后在返回时打印即可。
综上所述,以下是改进后的代码:
阅读全文