Cod sursa(job #2819587)

Utilizator ciobyCiobanu Vlasie cioby Data 18 decembrie 2021 17:30:33
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");


int n,p,q,r;
int a[150][150];
int stiva[150];
int f[150];
int vf=0;
int v[150];
int rez[150];
int cnt=0;
bool aparut;

void citire()
{
    fin>>n>>p>>q>>r;
    int x,y;
    while(fin>>x>>y) a[x][y]=a[y][x]=1;
}

void dfs()
{
    stiva[++vf]=q;
    f[q]=1;
    while(vf>0)
    {
        int k=stiva[vf];
        bool gasit=0;
        bool aparut=0;
        for (int j=1;j<=n && !gasit;j++)
        {
            if (a[k][j]==1 && !f[j])
            {
                if (j==r) aparut=1;
                stiva[++vf]=j;
                gasit=1;
                f[j]=1;
                v[j]=k;
            }
        }
        if (!gasit) vf--;
    }
}

void rezolvare()
{
    dfs();
    int aux=p;
    while(aux!=q)
    {
        rez[++cnt]=aux;
        aux=v[aux];
    }
    rez[++cnt]=q;
    fout<<cnt<<'\n';
    for (int i=1;i<=cnt;i++)
        fout<<rez[i]<<' ';
}

int main()
{
    citire();
    rezolvare();
}