fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n , m ; // đỉnh và cạnh
  5. vector<int> ke[1001];
  6. int type[1001];
  7. int tmp ;
  8. bool visited[1001];
  9.  
  10. void inp(){
  11.     cin >> n >> m ; 
  12.     for(int i = 1 ; i <= m ; i++){
  13.         int x,y; 
  14.         cin >> x >> y;
  15.         ke[x].push_back(y);
  16.         ke[y].push_back(x);
  17.     }
  18. }
  19.  
  20. void ktao(){
  21.     memset(type,0,sizeof(type));
  22.     for(int i = 1 ; i <= n ; i++){
  23.         if(!ke[i].empty()){
  24.             type[i] = 1;
  25.             tmp = i ;
  26.             break;
  27.         }
  28.     }
  29. }
  30.  
  31. void marked(){
  32.     queue<int> q; 
  33.     q.push(tmp);
  34.     while(!q.empty()){
  35.         int p = q.front();
  36.         q.pop();
  37.         for(int x : ke[p]){
  38.             if(type[p] == 1){
  39.                 if(!type[x]){
  40.                     type[x] = 2;
  41.                     q.push(x);
  42.                 }
  43.             }
  44.             else if(type[p] == 2){
  45.                 if(!type[x]){
  46.                     type[x] = 1;
  47.                     q.push(x);
  48.                 }
  49.             }
  50.         }
  51.     }
  52. }
  53.  
  54. int main(){
  55.     inp();
  56.     ktao();
  57.     marked();
  58.     for(int i = 1 ; i <= n ; i++){
  59.         for(int j = i + 1 ; j <= n ; j++){ // Changed i to j here
  60.             if(type[i] == type[j]){
  61.                 for(int x : ke[i]){
  62.                     if(j == x){
  63.                         cout << "Khong phai do thi 2 phia \n";
  64.                         return -1;
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     cout << "Do thi 2 phia \n"; // Print this if the graph is bipartite
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
5 4
1 2
3 2
4 3
4 5
stdout 
Do thi 2 phia
https://ideone.com/6HufT5
[Graph]. Bài 35. Đồ thị 2 phía (Bipartite graph)
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!