Cod sursa(job #3146413)

Utilizator PitigoiOlteanEmanuelPitigoi Oltean Emanuel PitigoiOlteanEmanuel Data 20 august 2023 22:02:55
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
            #include <fstream>
            #include <vector>


            using namespace std;

            ifstream cin("dfs.in");
            ofstream cout("dfs.out");



            struct per
            {
                vector <int> dir;

            }v[1001];

            bool prez[100001];

            void dfs(int a)
            {
                for(int i=1;i<=v[a].dir[0];i++)
                {
                    if(prez[v[a].dir[i]]==0)
                    {
                       prez[v[a].dir[i]]=1;
                        dfs(v[a].dir[i]);
                    }

                }
            }

    int main()
    {
        int n,m;
        cin>>n>>m;
        for(int i=0;i<=n;i++)
        {
            v[i].dir.push_back(0);
        }
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            v[x].dir[0]++;
            v[x].dir.push_back(y);

            v[y].dir[0]++;
            v[y].dir.push_back(x);






        }
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(prez[i]==0)
            {
                cnt++;
                 dfs(i);

            }

        }
            cout<<cnt;

        return 0;
    }