Cod sursa(job #2419665)

Utilizator boguklMirzea Bogdan bogukl Data 9 mai 2019 10:34:51
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int main()
{
    int n;
    f>>n;
    vector < vector < int > > A(27);
    vector < string > C(n+1);
    vector < int > G(27,0);
    queue < int > Q;
    for (int i=1; i<=n; i++){
        string aux;
        f>>aux;
        C[i]=aux;
    }
    for (int i=1; i<n; i++){
        for (int j=i+1; j<=n; j++){
            int k=0, ok=0;
            while (k<C[i].size() && k<C[j].size() && !ok){
                A[C[i][k]-'a'].push_back(C[j][k]-'a');
                G[C[j][k]-'a']++;
                ok=1;
                k++;
            }
        }
    }
    for (int i=0;i<26;i++){
        if(G[i]==0)    Q.push(i);
    }
    while (!Q.empty()){
        int nod_curent=Q.front();
        Q.pop();
        g<<char(nod_curent+'a');
        for (auto i: A[nod_curent]){
            G[i]--;
            if (G[i]==0)    Q.push(i);
        }
    }
    return 0;
}