DFS: C ++ жүйесіндегі қосылған компоненттердің түйіндерін қалай көрсету керек

AC компоненттеріне тиесілі G сызбалары мен шыңдары бар қосылған құрамдастардың санын анықтау үшін ACM жарыстарының проблемасын жасаймын. Дәл қазір 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 жауаптар

Алгоритм шамамен шамамен:

  • График түйінін алыңыз.
  • Тікелей немесе жанама түрде барлық түйіндерді (екі бағыт бойынша) табыңыз.
  • Барлығын «өтіп кеткен» деп белгілеп, оларды жаңа құрамдас бөлікке қойыңыз.
  • емес өтетін және келесі процедураны қайталайтын келесі түйінді табыңыз.

Нәтиже - тек қана өзара қосылған түйіндер жиынтығы бар «компонент» деректер құрылымдарының жиынтығы (іске асыруымда 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 іздейтін түйіндер бір жиынтығында болғанша қайталаңыз. Сондай-ақ, сіз 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
қосылды