StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You should run bfs on every connected component. Simplest way to do this is to iterate over all vertices and if they weren't visited, then just call bfs on them.</p> <pre><code>bool is_bipartite() { for(int i = 0; i < numberVertex; i++) { if (visited[i] == 0 && !bfs(i)) { return false; } } return true; } </code></pre> <p>It is still linear because, you run bfs on every connected component once.</p> <pre><code>#include <cstdio> #include <vector> #include <queue> #include <iostream> using namespace std; #define MAX 1000 int numberVertex, numberEdges; int particion[MAX], visited[MAX]; vector< int > adjacencyMatrix[MAX]; bool bfs(int begin) { int i, origin, destination; queue< int > queueVertex; queueVertex.push(begin); particion[begin] = 1; // 1 left, visited[begin] = 1; // set adjacencyMatrixray while(!queueVertex.empty()) { origin = queueVertex.front(); queueVertex.pop(); for(i=0; i < adjacencyMatrix[origin].size(); i++) { destination = adjacencyMatrix[origin][i]; if(particion[origin] == particion[destination]) { return false; } if(visited[destination] == 0) { visited[destination] = 1; particion[destination] = 3 - particion[origin]; // alter 1 and 2 subsets queueVertex.push(destination); } } } return true; } bool is_bipartite() { for(int i=0; i< numberVertex; i++) { if (visited[i] == 0 && !bfs(i)) { return false; } } return true; } int main() { //freopen("tarea2.in", "r", stdin); int i,j, nodeOrigin, nodeDestination; scanf("%d %d", &numberVertex, &numberEdges); for(i=0; i<numberEdges; i++) { scanf("%d %d", &nodeOrigin, &nodeDestination); adjacencyMatrix[nodeOrigin].push_back(nodeDestination); adjacencyMatrix[nodeDestination].push_back(nodeOrigin); } if(is_bipartite()) { printf("Is bipartite\n"); for (j=0; j<numberVertex; j++){ cout<<j<<" "<<particion[j]<<endl; } } else {printf("Is not bipartite\n");} return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload