Cod sursa(job #1827938)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 12 decembrie 2016 16:07:08
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
vector <int>lv[100000];
vector <int>::iterator ii;
queue <int> corn;
int n,m;
bool used[100000];
int nodnou()
{

for(int i=1;i<=n;i++)

{
    if (used[i]==false) return i;
}
return false;



}

void popcornXD()
{
    int v[100000];
    int i=0;
    while(!corn.empty())
    {
        v[++i]=corn.front(); corn.pop();

    }
    sort(v+1,v+i+1);

    for(int j=i;j>=1;j--)
    {
        corn.push(v[j]);
    }

}
int main()
{
    FILE *f=fopen("dfs.in","r");

    int x,y;
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        lv[x].push_back(y);
        lv[y].push_back(x);


    }
    int ok=0;

        while(1)
         {
             x=nodnou();
             if(x==false)break;

             ok++;
             corn.push(x);
             used[x]=true;


   while(!corn.empty())
   {
       x=corn.front();
       cout<<x<<" ";
       corn.pop();
       for(ii=lv[x].begin();ii<lv[x].end();++ii)
       if(used[*ii]==false)
       {
           used[*ii]=true;
           corn.push(*ii);
       }
    popcornXD();



   }



         }
 FILE *g=fopen("dfs.out","w");
fprintf(g,"%d",ok);



    return 0;
}