Probleme de informatica - enunturi si rezolvari

Se da un graf orientat cu n varfuri si m arce prin lista arcelor. Determinati numarul minim de culori cu care se pot colora varfurile grafului astfel incat oricare doua varfuri adiacente sa aiba culori diferite.
Numerotand apoi culorile necesare, realizati o colorare a varfurilor grafului dat si precizati pentru fiecare varf culoare cu care il colorati.
De asemenea, pentru fiecare culoare afisati nodurile care se coloreaza cu ea.
Exemplu:
date.in
6 7
1 2
2 1
3 4
1 5
4 5
5 6
6 4
date.out
numarul minim de culori: 3
colorarea nodurilor:
1: 1
2: 2
3: 1
4: 3
5: 2
6: 1
pe culori:
culoarea 1: 1 3 6
culoarea 2: 2 5
culoarea 3: 4

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int A[50][50],n,m;
int x[50],p[50];

int culori(int s)
{
    int st,dr,i,x[50],j,c=1,maxx,t,gasit;
    st=dr=1;
    p[s]=1;
    x[1]=s;
    while(st<=dr)
    {
        for(i=1; i<=n; i++)
         {
            if(A[x[st]][i] && !p[i])
                {
                    dr++;
                    x[dr]=i;
                    maxx=0;
                    for(int k=1; k<=n; k++)
                        if((A[i][k] || A[k][i]) && p[k]>maxx) maxx=p[k];
                    t=1;
                    do {
                        gasit=0;
                        for(int k=1; k<=n; k++)
                        if((A[i][k] || A[k][i]) && p[k]==t) gasit=1;
                        if(gasit) t++;
                    }
                    while(t<=maxx && gasit);
                    if(gasit) p[i]=maxx+1;
                    else p[i]=t;
                }
         }
         st++;
    }
    for(i=1;i<=dr;i++) if(p[x[i]]>c) c=p[x[i]];
    return c;
}

int main()
{
    int x,y,c,maxx=0;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        A[x][y]=1;
    }
    for(int i=1;i<=n;i++)
    if(!p[i])
        { c=culori(i);
          if(c>maxx) maxx=c;
        }
    fout<<"numarul minim de culori: "<<maxx<<"\n";
    fout<<"colorarea nodurilor:\n";
    for(int i=1;i<=n;i++)
        fout<<i<<": "<<p[i]<<endl;
    fout<<"pe culori:\n";
    for(int i=1;i<=maxx;i++)
    {
        fout<<"culoarea "<<i<<": ";
        for(int j=1;j<=n;j++)
            if(p[j]==i) fout<<j<<" ";
        fout<<endl;
    }
    fin.close();
    fout.close();
    return 0;
}

24 apr 2024

Site-ul conține 884 de probleme rezolvate