Nu aveti permisiuni pentru a descarca fisierul grader_test3.in
Cod sursa(job #3149078)
Utilizator | Data | 6 septembrie 2023 10:23:45 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.93 kb |
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define fisier 1
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const double dancila = 3.14159265359; // PI
const double eps = 1e-9;
int n, m;
vector<vector<int> > v;
int cc;
bool viz[200002];
void dfs(int nod)
{
viz[nod] = 1;
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(!viz[vecin])
dfs(vecin);
}
}
int main()
{
#ifdef fisier
ifstream cin("dfs.in");
ofstream cout("dfs.out");
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
v.resize(n+1);
for(int i = 1; i <= m; ++i)
{
int a, b;
cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
}
for(int i = 1; i <= n; ++i)
if(!viz[i])
{
++cc;
dfs(i);
}
cout << cc;
return 0;
}