[Codeforces] E. Almost Regular Bracket Sequence

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Almost Regular Bracket Sequence
Source            : Codeforces
Category          : Data Structure
Algorithm         : Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e6 + 5;  
  
struct segmentTree  
{  
      int open, close;  
      segmentTree(int open = 0, int close = 0) : open(open), close(close) {}  
  
      void assignLeaf(char bracket)  
      {  
            open = close = 0;  
            if (bracket == '(') ++open;  
            else ++close;  
      }  
      void marge(const segmentTree &lchild, const segmentTree &rchild)  
      {  
            int mini = min(lchild.open, rchild.close);  
            open = lchild.open + rchild.open - mini;  
            close = lchild.close + rchild.close - mini;  
      }  
      bool isRegular()  
      {  
            return (open == 0 && close == 0);  
      }  
} Tree[maxn*4];  
  
int n;  
string s;  
  
void build(int node = 1, int a = 1, int b = n)  
{  
      if (a == b)  
      {  
            Tree[node].assignLeaf(s[a-1]);  
            return;  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      build(lft, a, mid);  
      build(rgt, mid+1, b);  
      Tree[node].marge(Tree[lft], Tree[rgt]);  
}  
  
void update(int node, int a, int b, int pos, char bracket)  
{  
      if (a > pos or b < pos) return;  
      if (a >= pos && b <= pos)  
      {  
            Tree[node].assignLeaf(bracket);  
            return;  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      update(lft, a, mid, pos, bracket);  
      update(rgt, mid+1, b, pos, bracket);  
      Tree[node].marge(Tree[lft], Tree[rgt]);  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> n >> s;  
      build();  
      int cnt = 0;  
      for (int i = 1; i <= n; i++)  
      {  
            char bracket = s[i-1];  
            if (bracket == '(')  
            {  
                  update(1, 1, n, i, ')');  
                  if (Tree[1].isRegular()) ++cnt;  
                  update(1, 1, n, i, '(');  
            }  
            else  
            {  
                  update(1, 1, n, i, '(');  
                  if (Tree[1].isRegular()) ++cnt;  
                  update(1, 1, n, i, ')');  
            }  
      }  
      cout << cnt;  
}  

[UVA] 12363 - Hedge Mazes

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12363 - Hedge Mazes
Source            : UVA Online Judge
Category          : Graph Theory
Algorithm         : Finding Bridge
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e5 + 5;  
  
struct Edge  
{  
      int v, e;  
      Edge(int v = 0, int e = 0) : v(v), e(e) {}  
};  
  
vector <Edge> graph[maxn];  
int maze_no[maxn];  
bool isBridge[maxn], vis[maxn];  
int dfsTime, dis[maxn], low[maxn];  
  
void findBridge(int u, int p, int maze)  
{  
      vis[u] = 1;  
      dis[u] = low[u] = ++dfsTime;  
      maze_no[u] = maze;  
      for (Edge E : graph[u])  
      {  
            int v = E.v;  
            int e = E.e;  
            if (v == p) continue;  
            if (!vis[v])  
            {  
                  findBridge(v, u, maze);  
                  low[u] = min(low[u], low[v]);  
                  if (dis[u] < low[v]) isBridge[e] = 1;  
            }  
            else  
            {  
                  low[u] = min(low[u], dis[v]);  
            }  
      }  
}  
  
int compo[maxn];  
  
void dfs(int u, int comp)  
{  
      compo[u] = comp;  
      for (Edge E : graph[u])  
      {  
            int v = E.v;  
            int e = E.e;  
            if (compo[v] or !isBridge[e]) continue;  
            dfs(v, comp);  
      }  
}  
  
void clean(int n)  
{  
      dfsTime = 0;  
      for (int i = 0; i < n; i++)  
      {  
            graph[i].clear();  
            dis[i] = 0;  
            low[i] = 0;  
            isBridge[i] = 0;  
            vis[i] = 0;  
            compo[i] = 0;  
            maze_no[i] = 0;  
      }  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int tnode, tedge, tquery;  
      while (cin >> tnode >> tedge >> tquery)  
      {  
            if (tnode + tedge + tquery == 0) break;  
            for (int e = 1; e <= tedge; e++)  
            {  
                  int u, v;  
                  cin >> u >> v;  
                  graph[u].emplace_back(v, e);  
                  graph[v].emplace_back(u, e);  
            }  
            int no = 0;  
            for (int i = 1; i <= tnode; i++)  
            {  
                  if (!vis[i]) findBridge(i, -1, ++no);  
            }  
            no = 0;  
            for (int i = 1; i <= tnode; i++)  
            {  
                  if (!compo[i]) dfs(i, ++no);  
            }  
            while (tquery--)  
            {  
                  int u, v;  
                  cin >> u >> v;  
                  if (maze_no[u] != maze_no[v] or compo[u] != compo[v]) cout << "N\n";  
                  else cout << "Y\n";  
            }  
            cout << "-\n";  
            clean(tnode+10);  
      }  
}