Pagini recente » Cod sursa (job #1223212) | Cod sursa (job #1869611) | Cod sursa (job #2628394) | Cod sursa (job #1096020) | Cod sursa (job #3134139)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("pang.in");
ofstream fout("pang.out");
vector<vector<int>>nod;
int intrari[100003];
int start[100003];
queue<int> q;
struct val1
{
int nrrelicve=0;
bool vizitat=false;
bool isrelicva=false;
};
val1 val[100003];
struct maxim
{
int valmax=-1;
int pozvalmax;
};
maxim maxrelicve[100003];
int nrvizite[100003];
int tati[100003];
struct lol
{
int poz;
bool corect=false;
};
lol bfs(int intrari[100003],int start[100003],int k,int nr,int nrvizite[100003],maxim maxrelicve[100003],int tati[100003])
{
while (!q.empty()) {
q.pop();
}
lol boss;
for(int i=1; i<=nr; i++)
{
q.push(start[i]);
}
while(!q.empty())
{
int frn=q.front();
q.pop();
for(int i=0; i<nod[frn].size(); i++)
{
if(val[nod[frn][i]].isrelicva==true)
{
val[nod[frn][i]].nrrelicve=val[frn].nrrelicve+1;
}
else
{
val[nod[frn][i]].nrrelicve=val[frn].nrrelicve;
}
if(val[nod[frn][i]].nrrelicve>=maxrelicve[nod[frn][i]].valmax)
{
maxrelicve[nod[frn][i]].valmax=val[nod[frn][i]].nrrelicve;
maxrelicve[nod[frn][i]].pozvalmax=frn;
}
if(val[nod[frn][i]].vizitat==false)
{
nrvizite[nod[frn][i]]++;
}
if(nrvizite[nod[frn][i]]==intrari[nod[frn][i]])
{
val[nod[frn][i]].vizitat=true;
val[nod[frn][i]].nrrelicve=maxrelicve[nod[frn][i]].valmax;
tati[nod[frn][i]]=maxrelicve[nod[frn][i]].pozvalmax;
q.push(nod[frn][i]);
if(val[nod[frn][i]].nrrelicve==k)
{
boss.poz=nod[frn][i];
boss.corect=true;
return boss;
}
}
}
}
return boss;
}
int main()
{
int t,n,m,k;
fin>>t;
for(int i=1; i<=t; i++)
{
int m1,m2;
fin>>n>>m>>k;
nod.clear();
nod.resize(n+1);
for(int j=1; j<100003; j++)
{
maxrelicve[i].valmax=-1;
nrvizite[i]=0;
intrari[i]=0;
val[i].vizitat=0;
val[i].isrelicva=0;
val[i].nrrelicve=0;
start[i]=0;
}
for(int j=0; j<m; j++)
{
fin>>m1>>m2;
nod[m1].push_back(m2);
intrari[m2]++;
}
int pozrelicva;
for(int j=1; j<=k; j++)
{
fin>>pozrelicva;
val[pozrelicva].isrelicva=true;
val[pozrelicva].nrrelicve=1;
}
int nr=0;
for(int j=1; j<=n; j++)
{
if(intrari[j]==0)
{
nr++;
start[nr]=j;
}
}
int ok=0;
lol rasp=bfs(intrari,start,k,nr,nrvizite,maxrelicve,tati);
if( rasp.corect==true)
{
ok=1;
fout<<"Da"<<"\n";
}
else
fout<<"Nu"<<"\n";
int raspf[100003];
int num=1;
int aux=rasp.poz;
if(ok==1)
{
raspf[num]=aux;
while(tati[aux]>0)
{
num++;
raspf[num]=tati[aux];
aux=raspf[num];
}
for(int j=num; j>=1; j--)
{
if(val[raspf[j]].isrelicva==true)
fout<<raspf[j]<<" ";
}
fout<<"\n";
}
}
}