Cod sursa(job #3146405)

Utilizator PitigoiOlteanEmanuelPitigoi Oltean Emanuel PitigoiOlteanEmanuel Data 20 august 2023 21:06:10
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
            #include <fstream>


            using namespace std;

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



            struct per
            {
                int dir[2001];

            }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=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            v[x].dir[0]++;
            v[x].dir[v[x].dir[0]]=y;

            v[y].dir[0]++;
            v[y].dir[v[y].dir[0]]=x;






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

            }

        }
            cout<<cnt;

        return 0;
    }