DFS: C ++ da biriktirilgan komponentlarning tugunlarini qanday ko'rsatish mumkin?

Men har bir tarkibiy qismga tegishli G va vertikatlarga ega bo'lgan ulangan tarkibiy qismlar sonini aniqlash uchun ACM tanlovlari haqida muammo qilyapman. DFS algoritmi bilan ishlagansiz, lekin indirected grafigining bog'liq qismlarining sonini hisoblab chiqqandim (muammoning qattiq qismi), lekin har bir komponentga tegishli tugunlarni ko'rsatish yoki tugun yozuvlarini yozish uchun hech narsa haqida o'ylay olmayman.

Kiritish: 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

Chiqish: 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."

Misol:

Kiritish:

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

Chiqish:

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

Mana mening kodim:

#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

Men har bir bog'langan komponentga tegishli bo'lgan tugunlarni xotirani qanday saqlashni, yoki saqlash uchun ishlatiladigan tuzilmani, kodni qanday o'zgartirish kerakligini shubha bilan qarashim kerakmi? Men psevdokoddagi takliflarni, g'oyalarni yoki har qanday dasturni eshitishni xohlayman. Barchaga rahmat

5

4 javoblar

Algoritm taxminan:

  • Grafik tugunni oling.
  • To'g'ridan-to'g'ri yoki bilvosita unga bog'langan barcha tugunlarni toping (har ikki yo'nalishda ham).
  • Barchasini "o'tib ketgan" deb belgilang va ularni yangi komponentga joylashtiring.
  • emas va keyingi jarayonni takrorlash uchun keyingi tugunni toping.

Natija - bu "komponent" ma'lumotlar tuzilmalari to'plamidir (mening ilovamda std :: vector s), ularning har biri alohida o'zaro bog'langan tugunlar to'plamini o'z ichiga oladi.

Muhokamalar:

  • Grafikni "pastga" (ota-onadan bolalarga) va "yuqoriga" (bolalardan ota-onalarga) samarali tarzda aylanishi mumkin bo'lgan va shunga bog'liq bo'lgan barcha tugunlarni (har ikki yo'nalishda) topib olish kerak bo'lgan strukturada saqlash kerak. tugunlarni biz "o'tib ketgan" deb belgiladi. To'qimalarining doimiy tamsayı oralig'i bilan aniqlanganligi sababli, biz ushbu tuzilmani tasodifiy foydalanadigan std :: vector funktsiyalari yordamida samarali tarzda qurishimiz mumkin.
  • Kenar va tugunlar kontseptsiyasi ajratiladi, shuning uchun darajasida tekli "o'tish" bayrog'i, qancha boshqa tugunlar unga bog'liq bo'lmasin (ya'ni ko'p ota-ona va bola qirralari mavjud). Bu bizga rekursionni allaqachon yetib borilgan tugunlar uchun samarali tarzda kesishga imkon beradi.

Mana, ish kodi. E'tibor bering, ba'zi C ++ 11 funktsiyalari ishlatilgan bo'lsa-da, eski kompilyator ishlatilgan bo'lsa, ularni almashtirish oson bo'lishi kerak. Xatolarni ko'rib chiqish o'quvchi uchun mashq qilib qoldirildi.

#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;

    }

}

Ushbu dasturni qidiring ...

GraphComponents.exe < input.in > output.out

Bu erda input.in sizning savolingizda tasvirlangan ma'lumotlarni o'z ichiga oladi va output.out da kerakli natijani beradi.

2
qo'shib qo'ydi

yechim juda oson, siz ikkita kattalikdagi massivlarni e'lon qilishingiz kerak

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

So'ngra, DFSga qo'ng'iroq qilganingizda, har bir vertex vertices qatorida saqlanadi va ushbu komponentda saqlanadi

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
        }

Nihoyat, u umumiy komponentlarni chiqaradi va har bir vertexning komponenti bilan taqqoslanadigan birinchi komponentning qiymati bilan bayroqni yaratadi

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
qo'shib qo'ydi

2 ta tugunning ulanganligini tekshirish uchun umumiy algoritm:

  1. Barcha grafikangizni qirralarga bo'ling. Har bir tomonni to'siqqa qo'shing.
  2. Keyingi iteratsiya paytida, 2-qadamda qilgan chekkaning 2 tashqi tugunlari orasidagi chekka chizilgan. Ya'ni, yangi tugunlarni (ularning mos keladigan to'plamlari bilan) to'ldirib, asl qirrasi kelgan. (asosan, birlashma)
  3. Siz izlayotgan 2 tugunni bir xil to'siq bo'lguncha 2-takrorlang. Bundan tashqari, 1-bosqichdan so'ng (2 tugunni ulashgan bo'lsa) tekshirishingiz kerak bo'ladi.

Avval sizning tugunlaringiz o'z majmuida bo'ladi,

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

Algoritm siljishlar bilan birga rivojlanib, uni birlashtirganda, u kirishni nisbatan qisqartiradi.

Yuqoridagi misolda men O2 va O2 orasida yo'l borligini ko'rishni istardim. Men bu yo'lni barcha qirralarni birlashtirishdan keyin oxirigacha topdim. Ba'zi grafikalar alohida qismlarga ega bo'lishi mumkin (uzilib qolgan), bu sizning oxirida bitta to'plamga ega bo'lmaydi. Bunday holatda ushbu algoritmni bog'lanish uchun test qilish va hatto grafadagi komponentlarning sonini hisoblash uchun ishlatishingiz mumkin. Komponentlarning soni algoritm tugashi bilanoq siz olishingiz mumkin bo'lgan guruhlar soni.

Mumkin grafika (yuqoridagi daraxt uchun):

o-o1-o-o-o2
  |    |
  o    o
       |
       o
0
qo'shib qo'ydi

Quyidagi kabi tarkibiy qismlarni saqlashingiz mumkin:

typedef vector Component;
vector components;

kodni o'zgartiring:

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
    }
}

Endi 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
qo'shib qo'ydi