Cod sursa(job #2720452)

Utilizator LawrentiuTirisi Claudiu Lawrentiu Data 10 martie 2021 20:54:54
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream o("dfs.out");

void dfs(vector<int> *graph, int source, int *visited)
{
    vector<int> stack;
    int nod;
    visited[source] = 1;
    stack.push_back(source);
    while (!stack.empty())
    {
        nod = stack.back();
        stack.pop_back();
        for (vector<int>::iterator i = graph[nod].begin(); i != graph[nod].end(); ++i)
        {
            if (visited[*i]==0)
            {
                visited[*i] = 1;
                stack.push_back(*i);
            }
        }
    }
}

int main()
{
    int noduri, arce, a, b;
    f >> noduri >> arce;
    vector<int> graph[noduri + 1];
    for (int i = 0; i < noduri; i++)
    {
        f >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int visited[noduri + 1];
    memset(visited, 0, (noduri + 1) * sizeof(int));

    int n = 0;
    for (int i = 1; i <= noduri; i++)
    {
        if (visited[i]==0)
        {
            n++;
            dfs(graph, i, visited);
        }
    }
    o << n;
}