Cod sursa(job #2638255)

Utilizator alex.livadaruLivadaru Alexandru alex.livadaru Data 27 iulie 2020 16:18:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

const int kNmax = 100005;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

void fillStack(vector<bool> &visited,
stack<int> &s, int idx, vector<int> adj[kNmax]) {
    visited[idx] = true;

    for (auto i = adj[idx].begin(); i != adj[idx].end(); ++i) {
        if (!visited[*i]) {
            fillStack(visited, s, *i, adj);
        }
    }
    s.push(idx);
}

void res(vector<bool> &visited, vector<int> &aux,
int idx, vector<int> adj[kNmax]) {
    visited[idx] = true;
    aux.push_back(idx);

    for (auto i = adj[idx].begin(); i != adj[idx].end(); ++i) {
        if (!visited[*i]) {
            res(visited, aux, *i, adj);
        }
    }
}

int main() {
    int n, m, x, y;
    vector<int> adj[kNmax];

    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    vector<vector<int>> sol;
    vector<bool> visited(n + 1, 0);
    stack<int> s;

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            fillStack(visited, s, i, adj);
        }
    }

    for (int i = 1; i <= n; ++i) {
        visited[i] = 0;
    }

    while (!s.empty()) {
        int tmp = s.top();
        s.pop();

        if (!visited[tmp]) {
            vector<int> aux;
            res(visited, aux, tmp, adj);
            sol.push_back(aux);
        }
    }

    fout << sol.size();

    return 0;
}