Cod sursa(job #3293758)

Utilizator 11amIonescu-Vornicu Marta 11am Data 12 aprilie 2025 15:28:34
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
long long n, m, v[100], a[100][100];
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int x,y;
void dfs(int start)
{
    stack <int> s;
    s.push(start);
    while(!s.empty())
    {
        int nod_curent=s.top();
        bool gasit=false;
        for(int i=1;i<=n;i++)
        {
            if(v[i]==0 && a[nod_curent][i]==1)
            {
                gasit=true;
                s.push(i);
                v[i]=1;
                break;
            }
        }
        if(!gasit)
            s.pop();
    }
}
int main()
{
    int cnt=0;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
       fin >> x >> y;
       a[x][y] = 1;
       a[y][x] = 1;
    }

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