Cod sursa(job #2471996)

Utilizator minecraft3Vintila Valentin Ioan minecraft3 Data 11 octombrie 2019 21:23:47
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define PL pair<int,int>
#define PLL pair<long,long>
#define PD  pair<double,double>
#define PLD pair<long double,long double>

#define SORT_PFS(i,j,s1,s2) sort(i,j,[](auto&a,auto&b){return(a.first==b.first)?(a.second s2 b.second):(a.first s1 b.first);})
#define SORT_PSF(i,j,s1,s2) sort(i,j,[](auto&a,auto&b){return(a.second==b.second)?(a.first s2 b.first):(a.second s1 b.second);})
#define CMP(c) [](auto&a, auto&b){return(c);}

template<class T>inline pair<T,T>& swap(pair<T,T>&p){swap(p.first,p.second);return p;}

template<class T1,class T2>ostream&operator<<(ostream&os,pair<T1,T2>p){os<<p.first<<' '<<p.second;return os;}
template<class T1,class T2>ostream&operator>>(ostream&os,pair<T1,T2>p){os<<p.second<<' '<<p.first;return os;}
template<class T1,class T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<class T1,class T2>istream&operator<<(istream&is,pair<T1,T2>&p){is>>p.second>>p.first;return is;}

inline LL ipow(LL a,LL b){return(!b)?1:((b%2==0)?1:a)*ipow(a*a,b/2);}
inline LL ipow(LL a,LL b,LL m){return(!b)?1:((b%2==0)?1:a)*ipow(a*a%m,b/2, m)%m;}
inline LL ilog2(LL x){return (!x)?0:1+ilog2(x/2);}

#define pi 3.14159265358979323846
#define MIN(t) numeric_limits< t >::min()
#define MAX(t) numeric_limits< t >::max()

#define FOR(a,b) for(int a=0;a<b;++a)
#define FOR1(a,b) for(int a=1;a<=b;++a)
#define FORD(a,b) for(int a=b-1;a>=0;--a)
#define FORD1(a,b) for(int a=b;a>0;--a)

template<class Tv=int>void read_v(int&n,vector<Tv>&v){cin>>n;v.reserve(n);FOR(i,n)cin>>v[i];}

#define TEST freopen("test.in","r",stdin)
#define FIN(a) ifstream fin(a)
#define FOUT(a) ofstream fout(a)
#define FIO(a) ifstream fin(string(a)+".in");ofstream fout(string(a)+".out")
#define ARC list<int>

ARC v[200005];
bool viz[100005]{};
int n;

void DFS(int k) {
    viz[k] = true;
    for(auto& x : v[k])
        if(!viz[x]) DFS(x);
}

int main() {
    FIO("dfs");
    int m, x, y;
    fin >> n >> m;
    do {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    } while(--m);
    FOR1(i, n)
        if(!viz[i]) ++m, DFS(i);
    fout << m;
    return 0;
}