HackerEarth Rhezo and HackerEarth problem solution

In this HackerEarth Rhezo and HackerEarth problem solution Rhezo has just joined HackerEarth as an intern. Like most companies, HackerEarth too has a lot of computers and some departments. For efficient communication, it is very important that every computer can connect with each other in the same department, with the connection not being necessarily direct.

When each computer can connect with any other computer in the same department, that department is said to be happy. Initially all departments are happy.

Rhezo's friend Lonewolf wants to have some fun, and will cut some connection between any two computers for Q days. You being the Happy Manager of HackerEarth, need to tell for each of the Q days, if some department becomes unhappy.

HackerEarth Rhezo and HackerEarth problem solution.

#include<bits/stdc++.h>

using namespace std;
set<int> brid;
const int MAXN = 1e5+5;
vector< pair<int,int> > adj[MAXN];
int low[MAXN],disc[MAXN];
int tme=0;
bool vis[MAXN];
void DFS(int s, int par=-1) {
  vis[s]=true;
  ++tme;
  low[s]=disc[s]=tme;
  for(int i=0;i<(int)adj[s].size();i++) {
    int to=adj[s][i].first;
    int idx=adj[s][i].second;
    if(to==par) continue;
    if(!vis[to]) {
      DFS(to,s);
      low[s]=min(low[s],low[to]);
      if(low[to]>disc[s]) brid.insert(idx);
    }
    else low[s]=min(low[s],disc[to]);
  }
}
int main() {
  // freopen("TASK.in","r",stdin);  
  // freopen("TASK.out","w",stdout);
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=m;i++) {
    int x,y;
    scanf("%d%d",&x,&y);
    adj[x].push_back(make_pair(y,i));
    adj[y].push_back(make_pair(x,i));
  }
  for(int i=1;i<=n;i++) if(!vis[i]) DFS(i);
  int q;
  cin>>q;
  while(q--) {
    int x;
    scanf("%d",&x);
    if(brid.find(x)!=brid.end()) printf("Unhappy\n");
    else printf("Happy\n");
  }
  return 0;
}

Second solution

#include<bits/stdc++.h>
#define siz 100005
using namespace std;
vector<int>v[siz];
bool vis[siz];
int n,num[siz],parent[siz],low[siz];
stack<int>st;
set<pair<int,int> >ans;
set<pair<int,int> >::iterator it;
void dfs(int u)
{
  static int time=1;
  int children=0;
  vis[u]=1;
  num[u]=low[u]=time++;
  for(int i=0;i<v[u].size();i++)
  {
    int curr=v[u][i];
    if(!vis[curr])
    {
      children++;
      parent[curr]=u;
      dfs(curr);
      low[u]=min(low[u],low[curr]);
      if(low[curr]>num[u]){ans.insert(make_pair(u,curr));ans.insert(make_pair(curr,u));}
    }
    else if(curr!=parent[u])
      low[u]=min(low[u],num[curr]);
  }
}
int main()
{
  int n,m,q;
  scanf("%d%d",&n,&m);
  int i,a[siz],b[siz];
  for(i=0;i<m;i++)
  {
    scanf("%d%d",&a[i],&b[i]);
    v[a[i]].push_back(b[i]);
    v[b[i]].push_back(a[i]);
  }
  for(i=1;i<=n;i++)
    if(!vis[i])
      dfs(i);
  scanf("%d",&q);
  while(q--)
  {
    int x;
    scanf("%d",&x);x--;
    if(ans.find(make_pair(a[x],b[x]))!=ans.end())printf("Unhappy\n");
    else printf("Happy\n");
  }
  return 0;
}