Cod sursa(job #2373446)

Utilizator RaulG99Gioanca Raul RaulG99 Data 7 martie 2019 13:32:37
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <fstream>

using namespace std;
int viz[100100];
ifstream f("dfs.in");
ofstream g("dfs.out");

int main()
{
    int n,m,nr=0;
    int x,y,i,top,lim;
    stack <int> S;

    f>>n>>m;

    vector <int> graf[n+10];

    for(i = 0; i < m; i++)
    {
        f>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    for(i=1; i <= n; i++)
        viz[i]=0;

    for(i = 1; i <= n; i++)
    {
        if(viz[i] == 0)
        {
            S.push(i);
            nr++;

            while(S.empty()==false)
            {
                top = S.top();
                S.pop();

                if(viz[top] == 0)
                {
                    viz[top] = 1;

                    lim = graf[top].size();

                    for(i = 0; i < lim; i++)
                    {
                        if(viz[graf[top][i]] == 0)
                        {
                            S.push(graf[top][i]);
                        }
                    }

                }
            }
        }
    }
    g<<nr;
    return 0;
}