Cod sursa(job #2285628)

Utilizator serban.ionescuionescu serban mihai serban.ionescu Data 18 noiembrie 2018 20:37:06
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include<deque>
#include<vector>
FILE*f;
FILE*g;

using namespace std;
const int alt=100005;
int v[alt],v1[alt],k,tat,n,m,x1,x2,i,j;
deque <int> deque1[alt];
void coada(int nr)
{
    while(!deque1[nr].empty())
    {
        tat=deque1[nr].front();
        deque1[nr].pop_front();
        if(v[tat]==0){k++;
        v1[tat]=k;v[tat]=1;}
        coada(tat);
    }


}
int main()
{f=fopen("sortaret.in","r");
g=fopen("sortaret.out","w");

    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x1,&x2);
        deque1[x1].push_front(x2);
    }
    for(i=1;i<=n;i++)
    {
        if(v[i]==0)
        {
            k++;
            v1[i]=k;
            v[i]=1;
            coada(i);
        }

    }k=0;
for(i=1;i<=n;i++)
{k++;for(j=1;j<=n;j++)
    if(v1[j]==k)
        fprintf(g,"%d ",j);}
    return 0;
}