Submission #779606

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <sstream> //string stream its useful!
#include<string>
#include<iostream>
#include<utility> //pair
#include <vector> // vector
#include <algorithm>    // swap,sort,binary_search
#include <functional>   // std::greater
#include <map> //map
#include<set> //set
#include<queue> //queue
#include<list> //list
#include<cmath>
#include<numeric>
#include<cassert>
#include <iomanip> //cout<<setprecision

typedef long long ll;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

using namespace std;
void omajinai() {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(15);
    //freopen("txt.csv","r",stdin);
}

vector<int> *root;
int *uf;
bool *ans;
bool *kotae;

int myfind(int n){
    if(uf[n]== n) return n;
    uf[n] = myfind(uf[n]);
    return uf[n];
}

void myunion(int x, int y){
    int a = myfind(x) , b = myfind(y);
    if(a == b) return;
    uf[b] = a;
    ans[a] = ans[a]||ans[b];
}

bool gett(int x){
    return ans[myfind(x)];
}

int main(){
    
    omajinai();
    int n,m,s; cin>>n>>m>>s;
    root = new vector<int>[n+1];
    uf = new int[n+1]; ans = new bool[n+1]; kotae = new bool[n+1];
    for(int i = 1; i<=n;i++){ uf[i] =  i;}
    fill(ans,ans+n+1,false); ans[s] = true;
    
    
    for(int i = 0 ; i< m; i++){
        int u,v;
        cin>>u>>v;
        if(!(u<=v)) swap(u,v);
        root[u].push_back(v);
    }
    
    for(int i = n;i>0;i--){
        for(int v:root[i]){
            myunion(i,v);
        }
        kotae[i] = gett(i);
    }
    
    for(int i = 1 ; i<=n;i++){ if(kotae[i]) cout<<i<<endl;}
    
}

Submission Info

Judge Result