Cod sursa(job #3004846)

Utilizator theninjaguy5Gheorghiu Mihail-Andrei theninjaguy5 Data 16 martie 2023 17:28:45
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

int n,m,bst,ops=0,jk;
int a[10000];
int b[10000];
int c[10000][10000];
int d[10000];
using namespace std;
ifstream f("sir.in");
ofstream g("sir.out");
void citire()
{
    for(int i=1;i<=n;i++)
    f>>a[i];
    for(int i=1;i<=m;i++)
    f>>b[i];
}
void afisare()
{
g<<bst<<'\n';
for(int i=bst;i>0;i--)
    g<<d[i]<<' ';
g<<'\n';
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)
        g<<c[i][j]<<' ';
    g<<'\n';
}
}
int main()
{int i,j;
    f>>n>>m;
citire();

for( i=1;i<=n;i++){
    for( j=1;j<=m;j++)
            if(a[i]==b[j]){
                c[i][j]=1+c[i-1][j-1];
            }
            else
                c[i][j]=max(c[i-1][j],c[i][j-1]);

}
for (i = m, j = n; i; ){}
        if (a[i] == b[j])
            d[++bst] = a[i], --i, --j;
        else if (c[i-1][j] < c[i][j-1])
            --j;
        else
            --i;

afisare();
    return 0;
}