fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 105;
  5. vector<int> adj[MAX];
  6. bool deleted[MAX]; // Đánh dấu đỉnh bị xóa tạm thời
  7. int n;
  8.  
  9. void readInput() {
  10.     cin >> n;
  11.     for (int i = 1; i <= n; i++) {
  12.         int k;
  13.         cin >> k;
  14.         for (int j = 0; j < k; j++) {
  15.             int v;
  16.             cin >> v;
  17.             adj[i].push_back(v);
  18.             adj[v].push_back(i);
  19.         }
  20.     }
  21. }
  22.  
  23. void dfs(int u, bool visited[]) {
  24.     visited[u] = true;
  25.     for (int v : adj[u]) {
  26.         if (!deleted[v] && !visited[v]) {
  27.             dfs(v, visited);
  28.         }
  29.     }
  30. }
  31.  
  32. int dem_so_tplt() {
  33.     bool visited[MAX] = {false};
  34.     int count = 0;
  35.     for (int i = 1; i <= n; i++) {
  36.         if (!deleted[i] && !visited[i]) {
  37.             count++;
  38.             dfs(i, visited);
  39.         }
  40.     }
  41.     return count;
  42. }
  43.  
  44. void tim_dinh_tru() {
  45.     vector<int> dt;
  46.     memset(deleted, false, sizeof(deleted));
  47.     int so_tplt_ban_dau = dem_so_tplt();
  48.  
  49.     for (int u = 1; u <= n; u++) {
  50.         // Đánh dấu đỉnh u bị xóa tạm thời
  51.         deleted[u] = true;
  52.         int tplt_moi = dem_so_tplt();
  53.         if (tplt_moi > so_tplt_ban_dau) {
  54.             dt.push_back(u);
  55.         }
  56.         // Khôi phục đỉnh u
  57.         deleted[u] = false;
  58.     }
  59.  
  60.     cout << dt.size() << endl;
  61.     for (int i : dt) cout << i << " ";
  62.     cout << endl;
  63. }
  64.  
  65. int main() {
  66.     readInput();
  67.     tim_dinh_tru();
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 5292KB
comments ()
stdin
copy 
5
2 2 3
2 1 3
3 1 2 4
2 3 5
1 4
stdout
copy 
2
3 4
https://ideone.com/vZCRA7
language:
C++ (gcc 8.3)
created:
5 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!