Cod sursa(job #1884568)

Utilizator Dupree7FMI Ciobanu Andrei Dupree7 Data 18 februarie 2017 21:42:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int N, M;
int viz[100001];
vector<int> v[100001];

void dfs(int nod)
{
    int i, x;
    stack<int> s;

    s.push(nod);
    viz[nod] = 1;

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

        for(int oth = 0; oth < int(v[x].size()); oth++)
            if(!viz[v[x][oth]])
                {
                viz[v[x][oth]] = 1;
                s.push(v[x][oth]);
                }
    }
}

int main()
{
    int i, c = 0;

    f >> N >> M;

    for(i = 0; i < M; i++)
    {
        int a, b;
        f >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(i = 1; i < N + 1; i++)
        if(!viz[i])
        {
            c++;
            dfs(i);
        }
    g << c;
    return 0;
}