堕人間の備忘録

フナチーズ・ドロップアウト

?UFT?

B - 駐車場

 

  1. #include<bits/stdc++.h>
  2. #define int long long int
  3. using namespace std;
  4.  
  5. static const int INF = 1LL << 60;
  6. static const int MAX_N = 200005;
  7.  
  8. int N;
  9. struct UF {
  10. int n, par[MAX_N];
  11. ///最初は全部根。
  12. void init(int pn){
  13. n = pn;
  14. for(int i=0;i<n;i++)par[i]=i;
  15. }
  16. ///木の根を求める
  17. int find(int x){
  18. if(par[x]==x){
  19. return x;
  20. }else{
  21. return par[x] = find(par[x]);
  22. }
  23. }
  24. ///xとyの属する集合を併合
  25. void unite(int x,int y){
  26. x = find(x);
  27. y=find(y);
  28. if(x==y)return;
  29.  
  30. par[x] = y;
  31. }
  32. ///xとyが同じねに属するか?
  33. bool same(int x,int y){
  34. return find(x)==find(y);
  35. }
  36. };
  37. ///グラフがつながっているか知りたいとき(例ARC056-Bの)
  38.  
  39. int m, s, ans[MAX_N];
  40. vector<int> G[MAX_N];
  41. UF uf;
  42. int n;
  43.  
  44. signed main(){
  45. ///cinの高速化
  46. cin.tie(0);
  47. ios::sync_with_stdio(false);
  48.  
  49. cin >> n >> m >> s;
  50. uf.init(n);
  51.  
  52. for(int i = 0; i < m; i++){
  53. int u,v;
  54. cin >> v >> u;
  55. G[u].push_back(v);
  56. ///無向グラフ
  57. G[v].push_back(u);
  58. }
  59. ///大きい方から?!(小さい方は埋まってるから.)
  60. for(int i = n; 0 < i; --i){
  61. for(int j=0; j < G[i].size(); j++){
  62. int to = G[i][j];
  63. if(to < i)continue;
  64. uf.unite(i, to);
  65. }
  66. ans[i] = uf.same(i, s);
  67. }
  68. for(int i = 1; i <= n; i++){
  69. if(!ans[i])continue;
  70. cout << i << endl;
  71. }
  72.  
  73. return 0;
  74. }