Cod sursa(job #2443810)

Utilizator MihclerioVladimir Chim Mihclerio Data 29 iulie 2019 16:03:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include<bits/stdc++.h>

#pragma gcc optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")

#define all(s) s.begin(),s.end()
#define rc(x) return cout<<x<<endl,0
#define forn(i,n) for(int i=0;i<int(n);i++)
#define len(a) (int) (a).size()

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

typedef long long ll;
typedef long double ld;

const int nmax=1e5+3;
const int mod=998244353;
const ll inf=0x3f3f3f3f3f3f3f3f;

/*===================*\
      comentarii:
\*===================*/

using namespace std;

vector<int> v[nmax];
bool f[nmax];

void DFS(int i) {
  f[i]=1;
  forn(j,v[i].size())
   if(!f[v[i][j]])
    DFS(v[i][j]);
}

int main()
{
  freopen("dfs.in","r",stdin);
  freopen("dfs.out","w",stdout);
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n,m,sol=0;
  cin>>n>>m;
  while(m--) {
    int x,y;
    cin>>x>>y;
    v[x].pb(y);
    v[y].pb(x);
  }
  for(int i=1;i<=n;i++)
  if(!f[i]) {
    DFS(i);
    sol++;
  }
  cout<<sol;
}