Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (11)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
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;
}

21 nov 2018
Site-ul conține 868 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian