2D VECTOR && DFS

#include <cstdio> #include <iostream> #include <string> #include <sstream> #include <numeric> #include <vector> #include <set> #include <queue> #include <stack> #include <random> #include <list> #include <iomanip> #include <algorithm> #include <cstdlib> #include <cstring> #include <cmath> #include <map> #include <deque> #include <math.h> #include <assert.h> #include <functional> #include <bits/stdc++.h> using namespace std; #define F first #define S second #define PB push_back #define MP make_pair #define ll long long #define EB emplace_back #define s(v) ((int)(v).size()) #define vLL(X) array<ll,X> #define FOR(I,A,B) for(ll I = (A); I <= (B); I++) #define RFOR(I,B,A) for(ll I = (B); I >=(A); I--) #define SORT(c) (sort(c.begin(),c.end())) #define aLL(X) X.begin(),X.end() #define deb(x) cout << x << endl #define scanE(a) scanf("%lld",&a) #define scanF(a,b) scanf("%lld%lld",&a,&b) #define deb1(x) cout << #x <<" "<< x << endl #define deb2(x,y) cout << #x <<" "<< x <<" "<< #y <<" "<< y << endl #define deb3(x,y,z) cout << #x <<" "<< x <<" "<< #y <<" "<< y <<" "<< z << " " << z <<"\n"; #define mem0(X) memset((X), 0, sizeof((X))) #define mem1(X) memset((X), -1, sizeof((X))) #define INS(v,v2) v.insert(v.end(), v2.begin(), v2.end()); #define BS(v,X) binary_search(v.begin(),v.end(),X) #define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin()) #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #define CASES int ___T; cin >> ___T; for(int cs=1;cs<=___T;cs++) #define Time cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<< "sec \n" #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); template<typename T>T gcd(T x, T y){if(y==0)return x;else return gcd(y,x%y);} template<class T> istream& operator>>(istream& is,vector<T>& a) {for(auto &p:a)is>>p;return is;} int ri(){int x;scanf("%i",&x);return x;} void rd(int&x){scanf("%i",&x);} void rd(long long&x){scanf("%lld",&x);} void rd(double&x){scanf("%lf",&x);}void rd(long double&x){scanf("%Lf",&x);} void rd(string&x){cin>>x;} void rd(char*x){scanf("%s",x);} template<typename T>void rd(vector<T>&x){for(T&p:x)rd(p);} ll fx4[] = {0, 0, 1, -1}; ll fy4[] = {1, -1, 0, 0}; ll fx8[] = {1, 1, 0, -1, -1, -1, 0, 1}; ll fy8[] = {0, 1, 1, 1, 0, -1, -1, -1}; using db = double; using LL = long long; using ull = unsigned long long; using pII = pair <int, int>; using pLL = pair <long long, long long>; const int mx = 1000005; const int inf = 2147483647; const ll INF = 0x3f3f3f3f3f3f3f3f;//1e18+9 const ll L_inf = 9223372036854775807; const int mod = 0x3f3f3f3f;//1e9+7 const int maxN = 2e5 + 1; bool isprime[mx]; ll POWER(ll y,ll z){ll res=1;while(z){if(z%2==1){res=(res*y)%mod;}y=(y*y)%mod;z>>=1LL;}return res;} void SIEVE(){for(ll i=2; i<=mx; i++)isprime[i]=true;for(ll i=3; i<=mx; i+=2){if(isprime[i]==true) {for(ll J=i*i; J<=mx; J+=i)isprime[J]=false;}}} ll node, edge; //ll COL[maxN]; //mem0(VISIT); ll cn = 0; ll n1, n2; vector<ll>v[maxN],COL(maxN,0); void DFS(ll x) { COL[x] = 2; for (ll i = 0; i<v[x].size(); ++i) { if(COL[v[x][i]]==0) { DFS(v[x][i]); } } } int main() { IOS #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif ll n, m; cin >> n >> m; while(m--) { cin >> n1 >> n2; v[n1].push_back(n2); v[n2].push_back(n1); } for (ll i = 1; i<=n; ++i) { if(COL[i]==0) { cn++; DFS(i); } } cout << cn - 1 << endl; }