Cod sursa(job #3123313)

Utilizator Alexander444Alex Chiriac Alexander444 Data 23 aprilie 2023 08:30:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>

using namespace std;

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

typedef vector<vector<int>> Graph;

void dfsRec(Graph &adj,int n,vector<bool> &visited,vector<int> &top,int &nr)
{
    visited[n]=true;
    for(auto neigh : adj[n])
        if(!visited[neigh])
            dfsRec(adj,neigh,visited,top,nr);
    top[--nr]=n;
}

void dfs(Graph &adj,int n)
{
    int nr=n,ret=0;
    vector<bool> visited(n+1,false);//daca a fost vizitat nodul
    vector<int> top(n);//ordinea topologica
    for(int i=1;i<=n;++i)
        if(!visited[i])
            ret++,dfsRec(adj,i,visited,top,nr);
    g<<ret<<'\n';
}

int main()
{
    int n,m,i,x,y;
    f>>n>>m;
    Graph adj(n+1,vector<int>());
    for(i=0;i<m;i++)
    {
        f>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(adj,n);

    f.close();
    g.close();
}