Cod sursa(job #3160512)

Utilizator RadushCordunianu Radu Radush Data 24 octombrie 2023 13:01:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.32 kb
#include<iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class GrafMatrix;
class Graf{
private:
    unordered_map<int,vector<int>> nod;
    int n;
    void dfs(int start, unordered_set<int> &v){
        if(v.find(start)!=v.end())
            return;
        v.insert(start);
        //fout<<start<<" ";
        for(int vec:nod[start])
            if(v.find(vec)==v.end())
                dfs(vec,v);
    }
    void add_neorientat(int st,int dr){
        if(nod.find(st)==nod.end())
            nod[st]=vector<int>();
        if(nod.find(dr)==nod.end())
            nod[dr]=vector<int>();
        nod[st].push_back(dr);
        nod[dr].push_back(st);
    }
    void add_orientat(int st, int dr){
        if(nod.find(st)==nod.end())
            nod[st]=vector<int>();
        nod[st].push_back(dr);
    }
public:
    Graf(int n){this->n=n;}
    Graf(){};
    void add(int o){
        int a,b;
        fin>>a>>b;
        if(o)
            add_orientat(a,b);
        else
            add_neorientat(a,b);
    }
    void dfs(int start){
        int cnt=1;
        unordered_set<int> v;
        dfs(start,v);
        for(int i=1;i<=n;i++)
            if(v.find(i)==v.end()) { dfs(i, v); cnt++; }
        fout<<cnt;
    }

    void afis(){
        for(int i=1;i<=n;i++){
            fout<<i<<") ";
                for(auto k:nod[i])
                    fout<<k<<" ";
            fout<<"\n";
        }
    }
    vector<int> bfs(int start){
        unordered_set<int> v;
        queue<int> q;
        vector<int> rez;
        for(int i=0;i<n;i++)
            rez.push_back(-1);
        rez[start-1]=0;

        v.insert(start);
        q.push(start);
        while(!q.empty()){
            int nod_cur=q.front();
            q.pop();

            for(int vec:nod[nod_cur])
                if(v.find(vec)==v.end()){
                    q.push(vec);
                    v.insert(vec);
                    rez[vec-1]=rez[nod_cur-1]+1;
                }
        }
        return rez;
    }
};

class GrafMatrix{
    vector<vector<int>> mat_ad;
    int n;
    void add_neorientat(){
        int a,b;
        fin>>a>>b;
        mat_ad[a][b]=1;
        mat_ad[b][a]=1;
    }
    void add_orientat(){
        int a,b;
        fin>>a>>b;
        mat_ad[a][b]=1;
    }
public:
    GrafMatrix(int n){
        this->n=n;
        mat_ad.resize(n+1,vector<int>(n+1));
    }
    void add(int orientat){
        if(orientat==0)
            add_neorientat();
        else
            add_orientat();

    }
    void afis(){
        for(int i=1;i<=n;i++){
            fout<<i<<") ";
            for(int j=1;j<=n;j++)
                if(mat_ad[i][j]==1)
                    fout<<j<<" ";
            fout<<"\n";
        }
    }
    void printMatrix(){
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                fout<<mat_ad[i][j]<<" ";
            fout<<"\n";
        }
    }
};
int main()
{
    int n,m,o=0;
    fin>>n>>m;
    Graf g(n);
    for(int i=1;i<=m;i++)
        g.add(o);
    g.dfs(1);
//    vector<int> rez=g.bfs(start);
//    for(auto x:rez)
//       fout<<x<<" ";

    return 0;
}