Pagini recente » Cod sursa (job #3265321) | Cod sursa (job #3289887) | Cod sursa (job #3293865) | Cod sursa (job #2450806) | Cod sursa (job #3294954)
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
class Task {
public:
static constexpr int NMAX = 1e5 + 5;
int n, m;
int sol;
vector<int> adj[NMAX];
void citire() {
FILE *in = fopen("dfs.in", "r");
fscanf(in, "%d %d", &n, &m);
for ( int i = 0 ; i < m ; i++ ) {
int src, dst;
fscanf(in, "%d %d", &src, &dst);
adj[src].push_back(dst);
adj[dst].push_back(src);
}
}
unordered_map<int, bool> vizitat;
int cnt = 0;
bool progress;
void dfs(int start) {
if ( vizitat.find(start) != vizitat.end() )
return;
vizitat[start] = true;
progress = true;
cnt++;
for ( int i = 0 ; i < adj[start].size() ; i++ ) {
if ( vizitat.find(adj[start][i]) == vizitat.end() )
dfs(adj[start][i]);
}
}
void solve() {
citire();
for ( int i = 1 ; i <= n ; i++ ) {
progress = false;
dfs(i);
if ( progress )
sol++;
if ( cnt == n )
break;
}
scriere();
}
void scriere() {
FILE *out = fopen("dfs.out", "w");
fprintf(out, "%d", sol);
}
};
int main() {
auto* t = new Task();
t->solve();
delete t;
}