[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);  
      }  
}