Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <string>
- using namespace std;
- bool dfs(int v, vector<vector<int>> mat, vector<int> &used) {
- used[v] = 1;
- for (int i = 0; i < mat[v].size(); i++) {
- if (used[mat[v][i]] == 0) {
- dfs(mat[v][i], mat, used);
- used[v] = 2;
- }
- }
- used[v] = 2;
- return true;
- }
- int main() {
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- int vertex, edges;
- fin >> vertex >> edges;
- vector<vector<int>> mat(vertex + 1, vector<int>());
- vector<int> used(vertex + 1);
- for (int i = 1; i < edges + 1; i++) {
- int a, b;
- fin >> a >> b;
- mat[a].push_back(b);
- mat[b].push_back(a);
- }
- int count = 0;
- for (int i = 1; i < used.size(); i++) {
- if (used[i] == 0) {
- dfs(i, mat, used);
- count++;
- }
- }
- fout << count;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement