ДФС: Як пазначыць вузлы падлучаных кампанентаў у 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< vertex ; ++i ){   //Loop through all possible vertex
                if( !visited[ i ] ){          //if we have not visited any one component from that node
                    dfs( i );                  //we travel from node i the entire graph is formed
                    totalComponents++;                   //increased amount of components
                }
            }
            printf("Case %d: %d component (s) connected (s)\n" ,cont++, totalComponents);

            for (j=0;j

У мяне ёсць сумненні аб тым, як пераносіць памяць вузлоў, якія належаць да кожнай кампаненце складнасці або структурам павінны выкарыстоўвацца для захоўвання, як я павінен змяніць свой код, каб зрабіць гэта?, Я хацеў бы пачуць прапановы, ідэі або любую рэалізацыю ў псевдокоде. дзякуючы ўсім

5

4 адказы

Алгарытм прыкладна:

    <�Літый> Атрымаць вузел графа.
  • Знайсці ўсе вузлы, прама ці ўскосна звязаныя з ім (у абодвух напрамках).
  • Адзначыць ўсе з іх, як «пройдзены» і змясціць іх у новы кампанент.
  • Знайсці наступны вузел, які <�моцны> не пройдзеных і паўтарыць працэс.

Вынік ўяўляе сабой набор структур дадзеных «кампанент» ( станд :: вектар ы ў маёй рэалізацыі), кожная з якіх утрымоўвае набор выключна злучаных паміж вузламі.

меркаванні:

  • Мы павінны захаваць графік ў структуры, якая можа быць эфектыўна пройденномом і «ўніз» (ад бацькоў да дзяцей) і «ўверх» (ад дзяцей да бацькоў) і рэкурсіўна знайсці ўсе падключаныя вузлы (у абодвух напрамках), маркіроўка вузлоў, як «праходзіцца», як мы ідзем. Бо вузлы ідэнтыфікаваныя празь няспынны дыяпазону цэлых лікаў, мы можам пабудаваць гэтую структуру эфектыўныя, проста выкарыстоўваючы ўласцівасці выпадковага доступу станд :: вектар .
  • <�Літый> Паняцце рэбраў і вузлоў падзеленыя, так што <�моцны> сінгл </моцны> «не пройдзены» сцяг можа існаваць на ўзроўні вузла, незалежна ад таго, колькі іншых вузлоў падлучаныя да яе (г.зн. незалежна ад таго, як многія бацькі і дзіця краю ёсць). Гэта дазваляе эфектыўна скараціць рэкурсіі для ўжо дасягнутых вяршыняў.

Вось працоўны код. Звярніце ўвагу, што былі выкарыстаныя некаторыя 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

Затым, калі вы тэлефануеце ў ДФС кожнай вяршыні захоўваецца ў масіве вяршыняў, і захоўваецца ў тым, што кампанент належыць

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 (толькі ў выпадку 2 вузлоў прымыкаюць).

На першым вашыя вузлы будуць кожны ў сваім наборы,

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
дададзена