diff options
| -rw-r--r-- | Sources/GraphAlgo.cpp | 35 |
1 files changed, 21 insertions, 14 deletions
diff --git a/Sources/GraphAlgo.cpp b/Sources/GraphAlgo.cpp index 7385763..71ed2c2 100644 --- a/Sources/GraphAlgo.cpp +++ b/Sources/GraphAlgo.cpp @@ -7,8 +7,14 @@ using std::vector; using std::queue; -void bfs(vector<vector<int>> &adj, int s, vector<int> &dist) { +bool bfsBipartiteCheck(vector<vector<int>> &adj, int s) { + if (adj[s].size() == 0) + return true; + + vector<int> dist(adj.size(), -1); + dist[s] = 0; queue<int> vertexQ; + vertexQ.push(s); while (!vertexQ.empty()) { @@ -17,19 +23,23 @@ void bfs(vector<vector<int>> &adj, int s, vector<int> &dist) { for (int i : adj[u]) { if (dist[i] == -1) { vertexQ.push(i); - dist[i] = dist[u] + 1; - } + if (dist[u] == 0) + dist[i] = 1; + if (dist[u] == 1) + dist[i] = 0; + } else if (dist[i] == dist[u]) + return false; } } + return true; } -int distance(vector<vector<int> > &adj, int s, int t) { - vector<int> dist(adj.size(), -1); - dist[s] = 0; - - bfs(adj, s, dist); - - return dist[t]; +int bipartite(vector<vector<int> > &adj) { + bool bipartiteCheckNodes = bfsBipartiteCheck(adj, 0); + if (bipartiteCheckNodes) + return 1; + else + return 0; } int main() { @@ -42,10 +52,7 @@ int main() { adj[x - 1].push_back(y - 1); adj[y - 1].push_back(x - 1); } - int s, t; - std::cin >> s >> t; - s--, t--; - std::cout << distance(adj, s, t); + std::cout << bipartite(adj); } //TEST(Acyclicity, ac1) { |