4651. PTwPZ Zamek [PTWPZ078]

Zadanie:
https://pl.spoj.com/problems/PTWPZ078

Skrócony opis problemu:

Mamy liczby $n$ i $m$ ($n,m \le 10000$) oznaczające odpowiednio ilość wierzchołków i krawędzi w digrafie oraz liczbę $t$ ($t<21$) i $t$ liczb oznaczających wierzchołki specjalne. Mamy wypisać z ilu wierzchołków (niekoniecznie zwykłych) da się dojść do wszystkich wierzchołków specjalnych.

Podejście naiwne:

Możemy dla każdego wierzchołka przechodzić graf zaczynając od niego (obojętnie czy BFSem czy DFSem) i sprawdzać do ilu wierzchołków specjalnych dojdzie. Jeśli dojdzie do $t$ takich wierzchołków, to inkrementujemy nasz wynik.

Złożoność: $O\left(n^2\right)$, bo dla n wierzchołków przechodzimy graf, a przechodzenia ma złożoność $O(n+m)$, a jako że $m=n$, to $O(n)$.

Podejście sprytne:

Poszukujemy ścieżek między danym wierzchołkiem specjalnym $x$, a pozostałymi wierzchołkami. Czemu więc nie zmienić kierunku tej ścieżki? Przechodźmy zatem graf, ale wychodząc tylko z wierzchołków specjalnych i poruszając się po grafie $G'$, w którym krawędzie $a \rightarrow b$ zamienimy na krawędzie $b \rightarrow a$. Wykonujemy zatem $t$ przeszukiwań grafu i w każdym inkrementujemy ilość wierzchołków specjalnych odwiedzonych przez wierzchołek $y$, jeśli z wierzchołka specjalnego $x$ dojdziemy do $y$.

Złożoność: $O(t \cdot n)$, bo mamy $t$ przeszukiwań o złożoności $O(n)$.

Ostateczny algorytm:

vector<int> tab[10009];
int ile[10009];
bool czy[10009];

void dfs(int v)
{
    ++ile[v];
    czy[v] = 1;
    for(int i = 0; i < tab[v].size(); ++i)
        if(!czy[tab[v][i]])
            dfs(tab[v][i]);
}

int main()
{
    int t, n, m, i, j, a, b, k[29];

    scanf("%d%d", &n, &m);
    while(m--)
        scanf("%d%d", &a, &b),
        tab[b].push_back(a);
    scanf("%d", &t);
    for(i = 0; i < t; ++i)
        scanf("%d", &k[i]);
    for(i = 1; i <= n; ++i)
        ile[i] = 0;
    for(i = 0; i < t; ++i)
    {
        for(j = 1; j <= n; ++j)
            czy[j] = 0;
        dfs(k[i]);
    }
    for(a = 0, i = 1; i <= n; ++i)
        a += ile[i]>=t;
    printf("%d\n", a);
}