sto provando a risolvere questo problema ma col mio codice il primo test case da 3 4 invece che 3 3 mentre gli altri 3 vanno e non riesco a capire perchè
questo è il mio codice:
#include <iostream>
#include <bits/stdc++.h>
#define MAXN 100000
using namespace std;
ifstream fin ("input.txt");
ofstream fout ("output.txt");
vector<int> adj[MAXN];
vector<int> visited(MAXN);
vector<int> singolo(MAXN);
long long giriMinimiPerLaLampadina=9999999; //i giri minori con la quale viene spenta la lampadina che sta venendo controllata dalla dfs
int giriMassimi=0; //i giri della lampadina che ci mette di più
void dfs(int x,int giriCorrenti)
{ //se non è stato visitato
if(visited[x]==0)
{
//lo visita
giriCorrenti++;
visited[x]=1;
//se non era singolo
if(singolo[x]==0)
{
//controlla gli altri
for(auto u:adj[x])
{
dfs(u,giriCorrenti);
}
//se era singolo
}else{
//guarda se ci ha messo meno giri rispetto alle altre strade prese
if(giriCorrenti<giriMinimiPerLaLampadina)
{
giriMinimiPerLaLampadina=giriCorrenti;
}
}
}
}
pair<int,int> svolgi()
{
//input
int N,A,B; //numero lampadine, numero interruttori singoli, numero interruttori doppi
fin>>N>>A>>B;
int lampadina1,lampadina2;
int lampadinaVincente=-1;
int giriLampadinaVincente=-1;
for(int i=0;i<A;i++)
{
fin>>lampadina1;
singolo[lampadina1]=1;
}
for(int i=0;i<B;i++)
{
fin>>lampadina1>>lampadina2;
adj[lampadina1].push_back(lampadina2);
adj[lampadina2].push_back(lampadina1);
}
//fine input
//per ogni lampadina
for(int i=0;i<N;i++)
{
//azzera visited
fill(visited.begin(),visited.end(), 0);
//chiama dfs
dfs(i,0);
//controlla se questa lampadina ha il percorso più lungo rispetto alle altre provate
if (giriMinimiPerLaLampadina>giriMassimi)
{
giriMassimi=giriMinimiPerLaLampadina;
lampadinaVincente=i;
giriLampadinaVincente=giriMassimi;
}
giriMinimiPerLaLampadina=9999999;
}
return make_pair(lampadinaVincente,giriLampadinaVincente);
}
int main()
{
fill(visited.begin(),visited.end(), 0);
int test;fin>>test;
for(int t=1;t<=test;t++)
{
pair<int,int> coppia=svolgi();
fout<<"Case #"<<t<<": "<<coppia.first<<" "<<coppia.second<<endl;
fill(singolo.begin(),singolo.end(), 0);
for(int i=0;i<100000;i++)
{
adj[i].clear();
}
giriMassimi=0;
}
}