fork download 
  1. // Solution 37 : Dao chim 
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int m , n ; // đảo(N) và cầu(m)
  5. vector<int> ke[1001];
  6. bool visited[1001];
  7. int ans = 0 ;
  8. vector<int> canh_cau; 
  9. void inp(){
  10.     cin >> n >> m ;
  11.     for(int i = 1 ; i <= m ; i++){
  12.         int x,y;
  13.         cin >> x >> y;
  14.         ke[x].push_back(y);
  15.         ke[y].push_back(x);
  16.     }
  17. }
  18. void DFS(int u){
  19.     visited[u] = true;
  20.     for(int x : ke[u]){
  21.         if(!visited[x]){
  22.             DFS(x);
  23.         }
  24.     }
  25. }
  26. int tplt(){
  27.     int ans = 0;
  28.     for(int i = 1 ; i<= n ; i++){
  29.         if(!visited[i]){
  30.             DFS(i);
  31.             ans++;
  32.         }
  33.     }
  34.     return ans;
  35. }
  36. void dinh_tru(){
  37.     int cc = tplt();
  38.     for(int i = 1 ; i <= n ; i++){
  39.         memset(visited,false,sizeof(visited));
  40.         visited[i] = true;
  41.         if(tplt() >> cc){
  42.             canh_cau.push_back(i);
  43.         }
  44.     }
  45. }
  46. int main(){
  47.     inp();
  48.     dinh_tru();
  49.     cout << canh_cau.size();
  50. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin 
6 8
1 3
6 1
6 3
4 1
6 4
5 2
3 2
3 5
stdout 
1
https://ideone.com/clpJzA
[Graph]. Bài 37. Quần đảo chìm
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!