Cod sursa(job #2243878)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 21 septembrie 2018 16:34:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <stack>
#include <vector>

using namespace std;

int main()
{

    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    int n, m, i, j, x, y, clus_no = 0;
    scanf("%d%d", &n, &m);
    vector<vector<int>> arcs(n+1);
    vector<int> clusters(n+1, -1);
    stack<int> st;

    for(i=1; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        arcs[x].push_back(y);
        arcs[y].push_back(x);
    }

    for(i=1; i<=n; ++i)
        if(clusters[i] == -1)
        {
            ++clus_no;
            clusters[i] = clus_no;
            st.push(i);

            while (!st.empty())
            {
                x = st.top();
                st.pop();

                for(j=0; j<arcs[x].size(); ++j)
                    if(clusters[arcs[x][j]] == -1)
                    {
                        clusters[arcs[x][j]] = clus_no;
                        st.push(arcs[x][j]);
                    }
            }
        }

    printf("%d\n", clus_no);

    fclose(stdin);
    fclose(stdout);

    return 0;
}