DFS: Як вказати вузли з'єднаних компонентів у C ++

Я роблю проблему змагань ACM для визначення кількості підключених компонентів, які мають неорієнтований граф G і вершини, що належать кожному компоненту. Уже виконано з алгоритмом DFS, підрахунок кількості підключених компонентів неорієнтованого графа (важка частина проблеми), але я не можу нічого придумати, щоб вказати вузли, що належать кожному компоненту або мати запис вузлів.

Вхідні дані: The first line of input will an integer C, which indicates the number of test cases. The first line of each test case contains two integers N and E, where N represents the number of nodes in the graph and E the number of edges in it. Then follow E lines, each with 2 integers I and J, where I and J represent the existence of an edge between node I and node J (0 ≤ I, J

Вихід: In the first line of each test case must display the following string "Case G: P component (s) connected (s)", where G represents the number of test case (starting at 1) and P the number of components connected in the graph. Then X lines, each containing the nodes belonging to a connected component (in order from smallest to largest) separated by spaces. After each test case should print a blank line. The output should be written in the "output.out."

Приклад:

Вхідні дані:

2
6 9
0 1
0 2
1 2
5 4
3 1
2 4
2 5
3 4
3 5
8 7
0 1
2 1
2 0
3 4
4 5
5 3
7 6

Вихід:

Case 1: 1 component (s) connected (s)
0 1 2 3 4 5

Case 2: 3 component (s) connected (s)
0 1 2
3 4 5
6 7

Ось мій код:

#include 
#include 
#include 
#include 
using namespace std;
vector adjacency[10000];
bool visited[10000];

/// @param Standard algorithm DFS
void dfs(int u){
    visited[ u ] = true;
    for( int v = 0 ; v < adjacency[u].size(); ++v ){
        if( !visited[ adjacency[u][v] ] ){
            dfs( adjacency[u][v] );
        }
    }
}

    int main(int argc, char *argv []){
    #ifndef ONLINE_JUDGE
    #pragma warning(disable: 4996)
        freopen("input.in", "r", stdin);
            freopen("output.out", "w", stdout);
    #endif

         ///enumerate vertices from 1 to vertex
        int vertex, edges , originNode ,destinationNode, i, j,cont =1;
        ///number of test cases
        int testCases;
        int totalComponents;
        scanf ("%d", &testCases);

        for (i=0; i

У мене є сумніви про те, як носити пам'ять вузлів, що належать кожному з'єднаному компоненті або структурі, повинні бути використані для зберігання, як я повинен змінити свій код, щоб зробити це? Дякую всім

5

4 Відповіді

Алгоритм приблизно такий:

  • Отримати вузол графіка.
  • Знайти всі вузли, які безпосередньо чи непрямо підключені до нього (в обох напрямках).
  • Позначте всі їх як "пройдені" і помістіть їх у новий компонент.
  • Знайдіть наступний вузол, який не проходить і повторює процес.

Результатом є набір "компонентних" структур даних ( std :: vector в моїй реалізації), кожен з яких містить набір виключно взаємозв'язаних вузлів.

Міркування:

  • Нам потрібно зберігати графік у структурі, яка може ефективно переходити як "вниз" (від батьків до дітей), так і "вгору" (від дітей до батьків) і рекурсивно знаходити всі пов'язані вузли (в обох напрямках), маркування вузлів як "пройдених", як ми йдемо. Оскільки вузли ідентифіковані безперервним діапазоном цілих чисел, ми можемо ефективно побудувати цю структуру лише за допомогою властивостей випадкового доступу std :: vector .
  • Поняття ребер і вузлів відокремлені, тому єдиний "прохідний" прапор може існувати на рівні вузла, незалежно від того, скільки інших вузлів підключено до нього (тобто незалежно від того, як є багато батьківських і дочірніх ребер). Це дає змогу ефективно вирізати рекурсію для вже досягнутих вузлів.

Ось робочий код. Зауважимо, що деякі функції C ++ 11 були використані, але їх слід легко замінити, якщо використовується старий компілятор. Обробка помилок залишається як вправа для читача.

#include 
#include 
#include 

// A set of inter-connected nodes.
typedef std::vector Component;

// Graph node.
struct Node {
    Node() : Traversed(false) {
    }
    std::vector Children;
    std::vector Parents;
    bool Traversed;
};

// Recursive portion of the FindGraphComponents implementation.
//   graph: The graph constructed in FindGraphComponents().
//   node_id: The index of the current element of graph.
//   component: Will receive nodes that comprise the current component.
static void FindConnectedNodes(std::vector& graph, unsigned node_id, Component& component) {

    Node& node = graph[node_id];
    if (!node.Traversed) {

        node.Traversed = true;
        component.push_back(node_id);

        for (auto i = node.Children.begin(); i != node.Children.end(); ++i)
            FindConnectedNodes(graph, *i, component);

        for (auto i = node.Parents.begin(); i != node.Parents.end(); ++i)
            FindConnectedNodes(graph, *i, component);

    }

}

// Finds self-connected sub-graphs (i.e. "components") on already-prepared graph.
std::vector FindGraphComponents(std::vector& graph) {

    std::vector components;
    for (unsigned node_id = 0; node_id < graph.size(); ++node_id) {
        if (!graph[node_id].Traversed) {
            components.push_back(Component());
            FindConnectedNodes(graph, node_id, components.back());
        }
    }

    return components;

}

// Finds self-connected sub-graphs (i.e. "components") on graph that should be read from the input stream.
//   in: The input test case.
std::vector FindGraphComponents(std::istream& in) {

    unsigned node_count, edge_count;
    std::cin >> node_count >> edge_count;

   //First build the structure that can be traversed recursively in an efficient way.
    std::vector graph(node_count);//Index in this vector corresponds to node ID.
    for (unsigned i = 0; i < edge_count; ++i) {
        unsigned from, to;
        in >> from >> to;
        graph[from].Children.push_back(to);
        graph[to].Parents.push_back(from);
    }

    return FindGraphComponents(graph);

}

void main() {

    size_t test_case_count;
    std::cin >> test_case_count;

    for (size_t test_case_i = 1; test_case_i <= test_case_count; ++test_case_i) {

        auto components = FindGraphComponents(std::cin);

       //Sort components by descending size and print them.
        std::sort(
            components.begin(),
            components.end(),
            [] (const Component& a, const Component& b) { return a.size() > b.size(); }
        );

        std::cout << "Case " << test_case_i <<  ": " << components.size() << " component (s) connected (s)" << std::endl;
        for (auto components_i = components.begin(); components_i != components.end(); ++components_i) {
            for (auto edge_i = components_i->begin(); edge_i != components_i->end(); ++edge_i)
                std::cout << *edge_i << ' ';
            std::cout << std::endl;
        }
        std::cout << std::endl;

    }

}

Викликати цю програму як ...

GraphComponents.exe < input.in > output.out

... де input.in містить дані у форматі, описаному у вашому запиті, і він дасть бажаний результат у output.out .

2
додано

рішення набагато простіше, необхідно оголосити два масиви розміром число вершин

int vertexNodes  [vertex]///array to store the nodes
int vertexComponents [vertex]///array to store the number of components

Потім при виклику DFS кожна вершина зберігається в масиві вершин, і зберігається на цьому компоненті, що належить

for( int i = 0 ; i < vertex ; ++i ) //iterate on all vertices
        {
                vertexNodes [i]=i;  //fill the array with the vertices of the graph
            if( !visited[ i ] )
            { ///If any node is visited DFS call
                    dfs(i);
                totalComponents++; ///increment number of components
            }
            vertexComponents [i]=totalComponents; ///is stored at each node component belongs to
        }

Нарешті, він друкує загальні компоненти і створює прапор зі значенням першого компонента, який порівнюється з компонентом кожної вершини

printf("Case %d: %d component (s) connected (s)\n" ,cont++, totalComponents);
int flag = vertexComponents[0]; ///Create a flag with the value of the first component
            for (k=0; k 
1
додано

Загальний алгоритм для перевірки підключення 2 вузлів:

  1. Розділіть весь графік на ребра. Додайте кожне ребро до набору.
  2. На наступній ітерації намалюйте ребра між 2 зовнішніми вузлами краю, які ви зробили на кроці 2. Це означає додавання нових вузлів (з відповідними наборами) до набору вихідних країв. (в основному встановлюється об'єднання)
  3. Повторіть 2, доки 2 вузли, які ви шукаєте, не збігаються. Вам також потрібно виконати перевірку після кроку 1 (тільки у випадку, якщо два вузли розташовані поруч).

Спочатку ваші вузли будуть кожен у своєму наборі,

o   o1   o   o   o   o   o   o2
 \/    \/    \/    \ /
 o o     o o     o o     o o
   \    /        \     /
   o o o o         o o o o 
      \               /
       o o1 o o o o o o2

Оскільки алгоритм прогресує і зливає набори, він відносно вдвічі зменшує вхід.

У наведеному вище прикладі я шукав, чи є шлях між o1 і o2. Я знайшов цей шлях тільки в кінці після об'єднання всіх ребер. Деякі графіки можуть мати окремі компоненти (роз'єднані), що спричиняє, що ви не зможете мати один набір в кінці. У такому випадку ви можете скористатися цим алгоритмом для перевірки зв'язності і навіть підрахувати кількість компонентів у графі. Кількість компонентів - це кількість наборів, які ви можете отримати, коли алгоритм закінчується.

Можливий графік (для дерева вище):

o-o1-o-o-o2
  |    |
  o    o
       |
       o
0
додано

Можна зберігати такі компоненти:

typedef vector Component;
vector components;

і змінити код:

void dfs(int u){
    components.back().push_back(u);
    visited[ u ] = true;
    for( int v = 0 ; v < adjacency[u].size(); ++v ){
        if( !visited[ adjacency[u][v] ] ){
            dfs( adjacency[u][v] );
        }
    }
}

for( int i = 0 ; i < vertex ; ++i ){   //Loop through all possible vertex
    if( !visited[ i ] ){          //if we have not visited any one component from that node
        components.push_back(Component());
        dfs( i );                  //we travel from node i the entire graph is formed
    }
}

зараз totalComponents є components.size ():

printf("Case %d: %d component (s) connected (s)\n" ,cont++, components.size());

        for (j=0;j

Note that the code is not tested. Include to get the sort function.

0
додано
IT KPI C/С++ новым годом
IT KPI C/С++ новым годом
747 учасників

Чат обсуждения С/С++. - Вопросы "напишите за меня лабу" - это оффтоп. - Оффтоп, флуд, оскорбления и вбросы здесь не приняты. - За нарушение - предупреждение или mute на неделю. - За спам и рекламу - ban. Все чаты IT KPI: https://t.me/itkpi/1147