Shashwat17's blog

By Shashwat17, history, 5 months ago, In English,

include <bits/stdc++.h>

include

using namespace std;

define watch(x) cout << (#x) << " is " << (x) << endl

define fast \

ios_base::sync_with_stdio(false); \
cin.tie(NULL);

define FOR(n) for(int i(0);i<n;++i)

define ASC(a,b) for(int i(a); i <=b; ++i)

define DESC(a,b) for(int i(a);i>=b;i--)

define WL(t) while(t--)

define SZ(a) int((a).size())

define PB push_back

define FF first

define SS second

define MP make_pair

define all(c) c.begin(), c.end()

define present(container, element) (container.find(element) != container.end())

// ^^for set,map etc

define cpresent(container, element) (find(all(container), element) != container.end())

// for vector,array etc

define tr(container, it) for (typeof(container.begin()) it = container.begin(); it != container.end(); it++)

define gcd(a, b) __gcd((a), (b))

define lcm(a, b) ((a) * (b)) / gcd((a), (b))

typedef long long LL; typedef long double LD; typedef vector vi; typedef vector vl; typedef map<char,int> mci; typedef pair<int, int> pii; typedef map<int,pii> ipii; const float INF = numeric_limits::infinity(); const int MOD = 1e9 + 7; const double PI = 3.14159265358979323846264338;

ifdef _DEBUG freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

endif

bool visited[1e5+1]; vector v[1e5+1];

void dfs(int a){ stack st; st.push(a); visited[a]=true; int h=st.top(); st.pop(); while(!st.empty()){ for(int x: v[a]){ if(!visted[x]) st.push(x); visited[x]=true; }

}

int main(){ int n,m; cin >> n >> m; FOR(m){ scanf("%d%d",x,y); v[x].PB(y); v[y].PB(x); } int k,cnt=0; cin >> k; dfs(k); for(int i(1);i<=n;++i){ if(visited[i]) cnt++; } cout << cnt << endl;

}

 
 
 
 
  • Vote: I like it
  • -39
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

fixed

#include <bits/stdc++.h>
using namespace std;

#define watch(x) cout << (#x) << " is " << (x) << endl
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
#define FOR(n) for(int i(0);i<n;++i)
#define ASC(a,b) for(int i(a); i <=b; ++i)
#define DESC(a,b) for(int i(a);i>=b;i--)
#define WL(t) while(t--)
#define SZ(a) int((a).size())
#define PB push_back
#define FF first
#define SS second
#define MP make_pair
#define all(c) c.begin(), c.end()
#define present(container, element) (container.find(element) != container.end())
// ^^for set,map etc

#define cpresent(container, element) (find(all(container), element) != container.end())
// for vector,array etc

#define tr(container, it) for (typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gcd(a, b) __gcd((a), (b))
#define lcm(a, b) ((a) * (b)) / gcd((a), (b))
typedef long long LL;
typedef long double LD;
typedef vector vi;
typedef vector vl;
typedef map < char, int > mci;
typedef pair < int, int > pii;
typedef map < int, pii > ipii;
const float INF = numeric_limits::infinity();
const int MOD = 1e9 + 7;
const double PI = 3.14159265358979323846264338;

#ifdef _DEBUG 
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
bool visited[(int)1e5 + 1];
vector <int> v[(int)1e5 + 1];

void dfs(int a) {
    stack <int> st;
    st.push(a);
    visited[a] = true;
    int h = st.top();
    st.pop();
    while (!st.empty()) {
        for (int x : v[a]) {
            if (!visited[x]) st.push(x);
            visited[x] = true;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    FOR(m) {
        int x, y;
        scanf("%d %d", &x, &y);
        v[x].PB(y);
        v[y].PB(x);
    }
    int k, cnt = 0;
    cin >> k;
    dfs(k);
    for (int i(1); i <= n; ++i) {
        if (visited[i]) cnt++;
    }
    cout << cnt << endl;
}