Advertisement
_rashed

SPOJ BIA

Jun 26th, 2022
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #define ll long long
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int OO = 1e9;
  6. const double EPS = 1e-9;
  7.  
  8. vector<vector<int>> graph;
  9. int n,m;
  10. vector<bool> vis;
  11. int v_cnt = 0;
  12.  
  13. void dfs(int curr, int ex) {
  14.     vis[curr] = 1;
  15.     v_cnt++;
  16.     for(int e : graph[curr]) {
  17.         if(e != ex && !vis[e]) {
  18.             dfs(e,ex);
  19.         }
  20.     }
  21. }
  22.  
  23. int main()
  24. {
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(NULL);
  27.     cout.tie(NULL);
  28.     int t = 10;
  29.     while(t--) {
  30.         cin >> n >> m;
  31.         graph.clear();
  32.         graph.resize(n);
  33.         vis.resize(n);
  34.         for(int i = 0; i < m; i++) {
  35.             int a,b;
  36.             cin >> a >> b;
  37.             a--,b--;
  38.             graph[a].push_back(b);
  39.         }
  40.         vector<int> ans;
  41.         for(int i = 0; i < n; i++) {
  42.             vis.assign(n,0);
  43.             v_cnt = 0;
  44.             dfs(0,i);
  45.             if(v_cnt != n-1) {
  46.                 ans.push_back(i+1);
  47.             }
  48.         }
  49.         cout << ans.size() << "\n";
  50.         for(int i = 0; i < ans.size(); i++) {
  51.             if(i)
  52.                 cout << " ";
  53.             cout << ans[i];
  54.         }
  55.         cout << "\n";
  56.     }
  57.  
  58.     return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement