Facebook
From Nemanja, 2 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 46
  1.  
  2. #include <iostream>
  3. #include <list>
  4. #include <stack>
  5. #include <vector>
  6. #include <cstdio>
  7. #define NIL -1
  8.  
  9. using namespace std;
  10.  
  11. int count = 0;
  12. vector <int> vektor[10003],v[10003];
  13.  
  14. class Edge {
  15.  
  16. public:
  17.  
  18.     int u;
  19.  
  20.     int v;
  21.  
  22.     Edge(int u, int v);
  23. };
  24.  
  25. Edge::Edge(int u, int v)
  26. {
  27.  
  28.     this->u = u;
  29.  
  30.     this->v = v;
  31. }
  32.  
  33.  
  34. // A class that represents an directed graph
  35.  
  36. class Graph {
  37.  
  38.     int V; // No. of vertices
  39.  
  40.     int E; // No. of edges
  41.  
  42.     list<int>* adj; // A dynamic array of adjacency lists
  43.  
  44.  
  45.  
  46.     // A Recursive DFS based function used by BCC()
  47.  
  48.     void BCCUtil(int u, int disc[], int low[],
  49.  
  50.                  list<Edge>* st, int parent[]);
  51.  
  52.  
  53.  
  54. public:
  55.  
  56.     Graph(int V); // Constructor
  57.  
  58.     void addEdge(int v, int w); // function to add an edge to graph
  59.  
  60.     void BCC(); // prints strongly connected components
  61. };
  62.  
  63.  
  64.  
  65. Graph::Graph(int V)
  66. {
  67.  
  68.     this->V = V;
  69.  
  70.     this->E = 0;
  71.  
  72.     adj = new list<int>[V];
  73. }
  74.  
  75.  
  76.  
  77. void Graph::addEdge(int v, int w)
  78. {
  79.  
  80.     adj[v].push_back(w);
  81.  
  82.     E++;
  83. }
  84.  
  85.  
  86. // A recursive function that finds and prints strongly connected
  87. // components using DFS traversal
  88. // u --> The vertex to be visited next
  89. // disc[] --> Stores discovery times of visited vertices
  90. // low[] -- >> earliest visited vertex (the vertex with minimum
  91. // discovery time) that can be reached from subtree
  92. // rooted with current vertex
  93. // *st -- >> To store visited edges
  94.  
  95. void Graph::BCCUtil(int u, int disc[], int low[], list<Edge>* st,
  96.  
  97.                     int parent[])
  98. {
  99.  
  100.     // A static variable is used for simplicity, we can avoid use
  101.  
  102.     // of static variable by passing a pointer.
  103.  
  104.     static int time = 0;
  105.  
  106.  
  107.  
  108.     // Initialize discovery time and low value
  109.  
  110.     disc[u] = low[u] = ++time;
  111.  
  112.     int children = 0;
  113.  
  114.  
  115.  
  116.     // Go through all vertices adjacent to this
  117.  
  118.     list<int>::iterator i;
  119.  
  120.     for (i = adj[u].begin(); i != adj[u].end(); ++i) {
  121.  
  122.         int v = *i; // v is current adjacent of 'u'
  123.  
  124.  
  125.  
  126.         // If v is not visited yet, then recur for it
  127.  
  128.         if (disc[v] == -1) {
  129.  
  130.             children++;
  131.  
  132.             parent[v] = u;
  133.  
  134.             // store the edge in stack
  135.  
  136.             st->push_back(Edge(u, v));
  137.  
  138.             BCCUtil(v, disc, low, st, parent);
  139.  
  140.  
  141.  
  142.             // Check if the subtree rooted with 'v' has a
  143.  
  144.             // connection to one of the ancestors of 'u'
  145.  
  146.             // Case 1 -- per Strongly Connected Components Article
  147.  
  148.             low[u] = min(low[u], low[v]);
  149.  
  150.  
  151.  
  152.             // If u is an articulation point,
  153.  
  154.             // pop all edges from stack till u -- v
  155.  
  156.             if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
  157.  
  158.                 while (st->back().u != u || st->back().v != v) {
  159.                     vektor[count+1].push_back(st->back().u);vektor[count+1].push_back(st->back().v);
  160.                 //    cout << st->back().u << "--" << st->back().v << " ";
  161.  
  162.                     st->pop_back();
  163.  
  164.                 }
  165.  
  166.                 vektor[count+1].push_back(st->back().u);vektor[count+1].push_back(st->back().v);
  167.               //  cout << st->back().u << "--" << st->back().v;
  168.  
  169.                 st->pop_back();
  170.  
  171.   //              cout << endl;
  172.  
  173.                 count++;
  174.  
  175.             }
  176.  
  177.         }
  178.  
  179.  
  180.  
  181.         // Update low value of 'u' only of 'v' is still in stack
  182.  
  183.         // (i.e. it's a back edge, not cross edge).
  184.  
  185.         // Case 2 -- per Strongly Connected Components Article
  186.  
  187.         else if (v != parent[u]) {
  188.  
  189.             low[u] = min(low[u], disc[v]);
  190.  
  191.             if (disc[v] < disc[u]) {
  192.  
  193.                 st->push_back(Edge(u, v));
  194.  
  195.             }
  196.  
  197.         }
  198.  
  199.     }
  200. }
  201.  
  202.  
  203. // The function to do DFS traversal. It uses BCCUtil()
  204.  
  205. void Graph::BCC()
  206. {
  207.  
  208.     int* disc = new int[V];
  209.  
  210.     int* low = new int[V];
  211.  
  212.     int* parent = new int[V];
  213.  
  214.     list<Edge>* st = new list<Edge>[E];
  215.  
  216.  
  217.  
  218.     // Initialize disc and low, and parent arrays
  219.  
  220.     for (int i = 0; i < V; i++) {
  221.  
  222.         disc[i] = NIL;
  223.  
  224.         low[i] = NIL;
  225.  
  226.         parent[i] = NIL;
  227.  
  228.     }
  229.  
  230.  
  231.  
  232.     for (int i = 0; i < V; i++) {
  233.  
  234.         if (disc[i] == NIL)
  235.  
  236.             BCCUtil(i, disc, low, st, parent);
  237.  
  238.  
  239.  
  240.         int j = 0;
  241.  
  242.         // If stack is not empty, pop all edges from stack
  243.  
  244.         while (st->size() > 0) {
  245.  
  246.             j = 1;
  247.             vektor[count+1].push_back(st->back().u);vektor[count+1].push_back(st->back().v);
  248.  
  249.            // cout << st->back().u << "--" << st->back().v << " ";
  250.  
  251.             st->pop_back();
  252.  
  253.         }
  254.  
  255.         if (j == 1) {
  256.  
  257. //            cout << endl;
  258.  
  259.             count++;
  260.  
  261.         }
  262.  
  263.     }
  264. }
  265.  
  266.  
  267. int br,n,a,b,s,d,brizlaz,nizizlaz[10005],nizizlazdir[10005];
  268. bool pos2[10005],pos[10005];
  269. bool dfsodsec(int poc){
  270.     pos[poc]=1;
  271.     bool ret=0;
  272.     bool q=0;
  273.     if(poc==d){pos[poc]=0;return 1;}
  274.     for(int i=0;i<v[poc].size();i++){
  275.         if(v[poc][i]==d){
  276.             v[d].push_back(poc);
  277.             ret=1;
  278.         }
  279.         if(!pos[v[poc][i]]){
  280.  
  281.             q=dfsodsec(v[poc][i]);
  282.             if(!q){
  283.                 v[poc].erase(v[poc].begin()+i);
  284.                 i--;
  285.             }
  286.             else ret=1;
  287.         }
  288.     }
  289.     pos[poc]=0;
  290.     return ret;
  291. }
  292. void dfs(int poc){
  293.     nizizlazdir[poc]=true;
  294.     pos2[poc]=1;
  295.     for(int i=0;i<v[poc].size();i++){
  296.         if(!pos2[v[poc][i]]){
  297.             dfs(v[poc][i]);
  298.         }
  299.     }
  300.     pos2[poc]=0;
  301.     return ;
  302.  
  303. }
  304. int qwerty;
  305. void funl(){
  306.     qwerty=count;
  307. }
  308. #include <algorithm>
  309. int main()
  310. {
  311.     cin>>n;
  312.     Graph g(n);
  313.     scanf("%d %d",&a,&b);
  314.     while(a!=-1){
  315.     v[a].push_back(b);
  316.     v[b].push_back(a);
  317.     g.addEdge(a, b);
  318.     g.addEdge(b, a);
  319.     scanf("%d %d",&a,&b);
  320.     }
  321.     scanf("%d %d",&s,&d);
  322.     g.BCC();
  323.     dfsodsec(s);
  324.     dfs(s);
  325.     funl();
  326.     //for(int i=1;i<=20;i++)cout<<nizizlazdir[i]<<" ";cout<<endl;
  327.     for(int i=1;i<qwerty;i++){
  328.         br=0;
  329.         for(int k=0;k<vektor[i].size();k++){
  330.             //cout<<vektor[i][k]<<" ";
  331.             if(nizizlazdir[vektor[i][k]])br++;
  332.             if(br==2){
  333.                 for(int q=0;q<vektor[i].size();q++){nizizlaz[brizlaz+q+1]=vektor[i][q];}
  334.                 brizlaz+=vektor[i].size();
  335.                 continue;
  336.             }
  337.             //cout<<endl;
  338.         }
  339.     }
  340.     //cout<<endl;
  341.     sort(nizizlaz+1,nizizlaz+1+brizlaz);
  342.     for(int i=1;i<=brizlaz;i++){if(nizizlaz[i]!=nizizlaz[i-1])printf("%d ",nizizlaz[i]);}
  343.     cout<<endl;
  344.   /////  cout << "Above are " << count << " biconnected components in graph";
  345.     return 0;
  346. }
  347.