Advertisement
VladSmirN

Дискретная математика . Индивидуальное задание.

Mar 20th, 2021
360
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. const int MAXN = 20005;
  7. vector<vector<int> > g(MAXN);
  8. bool used[MAXN];
  9. int timer, tin[MAXN], fup[MAXN];
  10. vector<pair<int,int> >ans;
  11.  
  12. bool cmp(pair<int,int> a,pair<int,int>b)
  13. {
  14.     if(a.first < b.first) return true;
  15.     if(a.first == b.first)
  16.     {
  17.         return a.second < b.second;
  18.     }
  19.     return false;
  20. }
  21.  
  22. void dfs (int v, int p = -1)
  23. {
  24.  
  25.     used[v] = true;
  26.     tin[v] = fup[v] = timer++;
  27.     for (size_t i=0; i<g[v].size(); ++i)
  28.     {
  29.         int to = g[v][i];
  30.         if (to == p)  continue;
  31.         if (used[to])
  32.             fup[v] = min (fup[v], tin[to]);
  33.         else
  34.         {
  35.             dfs (to, v);
  36.             fup[v] = min (fup[v], fup[to]);
  37.             if (fup[to] > tin[v])
  38.                 ans.push_back({min(v,to),max(v,to)});
  39.         }
  40.     }
  41. }
  42.  
  43. void find_bridges(int n)
  44. {
  45.     timer = 0;
  46.     for (int i=0; i<n; ++i)
  47.         used[i] = false;
  48.     for (int i=0; i<n; ++i)
  49.         if (!used[i])
  50.             dfs (i);
  51. }
  52.  
  53. int main()
  54. {
  55.     ifstream filei("input.txt");
  56.     ofstream fileo("output.txt");
  57.     int N;
  58.     filei>>N;
  59.     int a;
  60.     int Count =0;
  61.     for(int i=0; i<N; ++i)
  62.         for(int j=0; j<N; ++j)
  63.         {
  64.             filei>>a;
  65.             if(a!=0 && a!=1)
  66.             {
  67.                 fileo<<"Error";
  68.                 return 0;
  69.             }
  70.             if(a==1)
  71.             {
  72.                 Count++;
  73.                 g[i].push_back(j);
  74.                 g[j].push_back(i);
  75.             }
  76.         }
  77.  
  78.     find_bridges(N);
  79.     sort(ans.begin(),ans.end(),cmp);
  80.     fileo<<ans.size()<<endl;
  81.     for(pair<int,int> edge:ans)
  82.     {
  83.         fileo<<edge.first+1<<"-"<<edge.second+1<<" ";
  84.     }
  85. }
  86.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement