Cod sursa(job #916824)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 16 martie 2013 22:00:30
Problema Pioni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<fstream>
using namespace std;
typedef struct celula{
          int nod;
          celula *next;
          }*lista;
lista graf[20005],v;
int i,j,n,m,t,juc[20005],lev[20005],grad[20005],go[20005],zero,pion[30005];
bool viz[20005];

void dfs(int nod){
     viz[nod]=1;
     if (grad[nod]==0) lev[nod]=1;
     else {
          for (lista p=graf[nod]; p; p=p->next) dfs(p->nod);
           int l=0,pos;
          for (lista p=graf[nod]; p; p=p->next)
           if (juc[p->nod]==0&&lev[p->nod]>l){ l=lev[p->nod]; pos=p->nod; }
          if (l>0) { juc[nod]=1; lev[nod]=l+1; go[nod]=pos; }
          else {
               l=1000000000; 
               for (lista p=graf[nod]; p; p=p->next)
                if (lev[p->nod]<l){ l=lev[p->nod]; pos=p->nod; }
               lev[nod]=l; go[nod]=pos;
               }
          }
}

int main(void){
    ifstream fin("pioni.in");
    ofstream fout("pioni.out");
    fin>>t>>n>>m;
    for (i=1; i<=m; ++i){
          int x,y; fin>>x>>y; ++grad[x];
          v=new celula; v->nod=y; v->next=graf[x]; graf[x]=v;
           }
 
    for (i=1; i<=n; ++i) 
     if (viz[i]==0) dfs(i);
       
    for (i=1; i<=t; ++i) {
       int k,mmax=0,poz; fin>>k; bool ok=0;
       for (j=1; j<=k; ++j) {
          int q; fin>>q; pion[j]=q;
          if (lev[q]==1) ++zero;
          if (lev[q]>mmax){ mmax=lev[q]; poz=q; }
          }
       if (juc[poz]==1){
                         fout<<"Nargy"<<"\n"; 
                         fout<<k-zero<<" ";
                         for (j=1; j<=k; ++j)
                          if (lev[pion[j]]>1) fout<<pion[j]<<" "<<go[pion[j]]<<" ";
                         fout<<"\n";
                         }
                         else fout<<"Fumeanu"<<"\n";
       
     }
 return(0);
}