Într-o clasă sunt n elevi, numerotați de la 1 la n, iar unii dintre ei pot cunoaște numerele de telefon ale altor elevi. Dirigintele dorește să-i anunțe pe elevi despre un eveniment deosebit și pentru aceasta poate să transmită informația doar elevilor din clasă cărora le cunoaște numărul de telefon, urmând ca aceștia să-și anunțe colegii cărora le cunosc numărul de telefon, aceștia să-și anunțe colegii cărora le cunosc numărul de telefon etc, astfel încât toți elevii să afle informația respectivă.
Determinați care sunt elevii din clasă care pot fi anunțați inițial astfel încât, toți elevii să fie în cele din urmă informați.
Răspunsuri la întrebare
Cerința
Într-o clasă sunt n elevi, numerotați de la 1 la n, iar unii dintre ei pot cunoaște numerele de telefon ale altor elevi. Dirigintele dorește să-i anunțe pe elevi despre un eveniment deosebit și pentru aceasta poate să transmită informația doar elevilor din clasă cărora le cunoaște numărul de telefon, urmând ca aceștia să-și anunțe colegii cărora le cunosc numărul de telefon, aceștia să-și anunțe colegii cărora le cunosc numărul de telefon etc, astfel încât toți elevii să afle informația respectivă.
Determinați care sunt elevii din clasă care pot fi anunțați inițial astfel încât, toți elevii să fie în cele din urmă informați.
Date de intrare
Programul citește de la tastatură numărul n de elevi și numărul m perechi de elevi, iar apoi lista de m perechi de elevi i j, cu semnificația că elevul i cunoaște numărul de telefon al elevului j.
Date de ieșire
Programul va afișa pe ecran în ordine crescătoare, separate prin exact un spațiu, numerele de ordine ale elevilor care pot fi contactați de diriginte astfel încât în final toți elevii să fie informați.
Restricții și precizări
- 1 ≤ n ≤ 100
- Pentru toate datele de test va exista cel puțin un elev care poate fi ales de diriginte.
Exemplu
Intrare
6 8
1 2
1 3
1 5
3 5
4 6
3 4
5 1
5 6
Ieșire
1 3 5
#include <bits/stdc++.h>
using namespace std;
int n , m , s , x , y , v[101] , d[101] , p , T[101] , L[101] , cnt;
vector <int> G[101];
void bfs(int s)
{
queue <int>Q;
Q.push(s);
v[s] = 1;
d[s] = 1;
while(!Q.empty())
{
int x = Q.front();
Q.pop();
for(int i : G[x])
if(!v[i])
{
d[i] = d[x] + 1;
Q.push(i);
v[i] = 1;
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= m ; i++)
{
cin >> x >> y;
G[x].push_back(y);
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= n ; j++)
d[j] = v[j] = 0;
bfs(i);
int ok = 0;
for(int j = 1 ; j <= n ; j++)
if(d[j] == 0 && j != i) ok++;
if(ok == 0) cout << i << " ";
}
}