graph_shareParent

#include <iostream>
#include <vector>
#include <fstream>
#define MAX  10001
using namespace std;

vector<int> g[MAX];//вектор для графа. номер строки соответствует вершине источнику,
                   //в векторе перечислены всевершины назначения
vector<int> gr[MAX];//транспонированный граф. нужен для обхода его в ширину, строится аналигично первому
int used[MAX];//вспомогательный массив для поиска в ширину

int bfs(int v)//алгоритм поиска в ширину
{
    int Q[MAX];//очередь на основе массива. такая реализация выбрана потому
                //что нам надо сохранять вершины в очереди, после того, как мы их оттуда извлекли
    int head = 0;//индекс головы
    int tail = 1;//и хвоста очереди
    Q[0] = v;//помещаем в очередь ту вершину, с которой начинаем обход
    used[v] = 1;//и помечаем её посещенной
    int from;
    int to;
    int count = 0;
    while(head < tail)//пока очередь не пуста
    {

        from = Q[head++];//вынимаем из очереди вершину
        for(unsigned int i=0; i<gr[from].size(); i++)//и начинаем оход её смежных вершин
        {
            to = gr[from][i];//получаем смежную вершину
            if(!used[to])//если она не посещена
            {
                used[to] = 1;//помечаем посещенной
                Q[tail++] = to;//кладем в очередь
                count++;//и увеличиваем счетчик пар вершин в общим предком
            }
        }
    }
//после обхода транспонированного графа надо обойти те вершины, которые были посещены.
//для этого перемещаем голову в начало очереди, не очищая её
    head = 0;
    while(head < tail)//обход аналогичен
    {
        from = Q[head++];
        for(unsigned int i=0; i<g[from].size(); i++)
        {
            to = g[from][i];
            if(!used[to])
            {
                used[to] = 1;
                Q[tail++] = to;
                count++;
            }
        }
    }
    return count + 1;//возвращаем количество вершин в общим предком+1, чтобы учесть что вершина достижима сама из себя
}

int main()
{
    setlocale(0, "");
    ifstream f("input.txt");
    if (!f)
    {
        cout << " We have a problem";
        return -1;
    }
    int n, m;//кол-во вершин и ребер
    int u, v;//считываемые вершины
    int result = 0;
    f>>n;//считываем из файла кол-во вершин
    f>>m;//и ребер
    for (int i=1;i<=m;i++)//цикл по ребрам
    {
        f>>u;//вершина источник
        f>>v;//вершина назначение
        g[u].push_back(v);//push_back - добавление значения в конец вектора
        gr[v].push_back(u);//здесь происходит транспонирование нашего графа
    }

    for(int i=1;i<= n;i++)//цикл по всем вершинам
    {
        for(int j=1;j<=n;j++)//обнуляем вспомогательный массив
            used[j] = 0;
        result = result + bfs(i);//и запускаем поиск
    }
    cout<<result;
}