#include
#include
#define llu long long unsigned
#define MAXSIZE 10000
#define pb push_back
using namespace::std;
typedef vector vi;
typedef pair < int, int > ii;
typedef vector < ii > vii;
typedef vector vvii;
typedef vector < vi > vvi;
//r2 keeps track of the no. of open window children of root of /**each**/ tree in the forest
map r2;
map aux_map;
vi tree;
vector track;
vector vs;
class disjoint_sets
{
public :
unordered_map parent;
unordered_map rank;
//constructor
disjoint_sets(deque &universe)
{
for(int x : universe)//for(auto it = universe.begin() ; it != universe.end() ; ++it) //: line no nodes req
{
parent[x] = x;
rank[x] = 0;
}
}
int find(int item)
{
if(parent[item] == item)
return item;
else return find(parent[item]);
}
void unite(int a, int b)
{
int a_parent = find(a);
int b_parent = find(b);
if(rank[a_parent] > rank[b_parent])
{
parent[b_parent] = a_parent;
rank[a_parent] += rank[b_parent];
}
else if(rank[a_parent] < rank[b_parent])
{
parent[a_parent] = b_parent;
rank[b_parent] += rank[a_parent];
}
else
{
parent[a_parent] = b_parent;
rank[b_parent] ++;
}
}
void disp()
{
for(pair < int, int > p : parent) //for(auto it = parent.begin() ; it != parent.end() ; ++it)
cout< &key, vector &vs) //function for second query
{
vs[x] = true;
int res = (key[x] == 1) ? 1 :0;
for(auto it : g[x])
if(!vs[it])
{
if(key[it] == 1)
{
vs[it] = true;
return 1;
}
res = dfs_fun(g, it, key, vs);
if(res) return res;
}
return res;
}
llu dfs(vvi &g, vector &vs, int v, vi &key)
{
vs[v] = true;
llu c = 1; //contribution of the node on which dfs has been called, ...we'll return c-1 later if this nodes window is closed
for(auto it = g[v].begin() ; it != g[v].end() ; ++it)
if(!vs[*it])
c += dfs(g, vs, *it, key); //increment c by the no of open window nodes rooted at c
if(key[v]) {
r2[v] = c ; //map r2 keeps track of no. of open window nodes rooted at each node of the graph
return c ;
}
{
r2[v] = c-1 ; //if the node has its window closed,adjust its contribution which was initiated as 1
return c-1;
}
}
void drought(vvi &g, vi &key, int V, vi &r1)
{
vs = vector (V+1, false);
vs[0] = true;
for(int i = 1 ; i <= V ; ++i)
if(!vs[i])
{
tree.pb(i); // the vector tree keeps track of root of each tree in the forest
r1.pb(dfs(g, vs, i, key)); //the vector r1 stores the no of 'open window' nodes rooted at each root of the forest including the status of root
}
}
long long unsigned calculate(vi tree, map &r2)
{
long long unsigned count = 0;
for(auto it : tree)
count += (r2[it]*(r2[it]-1))/2;
return count;
}
int main()
{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
srand(time(0));
track.reserve(50050);
tree.reserve(50050);
int V, E, s, d, w, st, auxi = 0;
cout<<"\nenter the no of nodes and edges :\t ";
cin>>V>>E;
deque aux;
for(int i = 0; i < V ; ++i) aux.pb(i+1);
disjoint_sets dso(aux);
for(int i = 0 ; i <= V ; ++i) r2[i] = 0;
tree.pb(0);
vi r1;
vi key(V+1);
vvi g(V+1);
//cout<<"\nenter the window status \n";
key[0] = 0;
for(int i = 1 ; i <= V ; ++i)
{
st = rand()%2;
key[i] = st;
}
/**cout<<"\nutilising rand(), the window status and links bw friends that have been formed are :\n";**/
for(int i = 1 ; i <= V ; ++i)
cout< open window children "< "< remaining;
// cout<<"\n3 cases for second answer :";
// cout<<"\n1.element has at least 1 open window child also there is some open window node rooted at the same root at which the element is hence at least the way between these 2 nodes connects 'em";
// cout<<"\n2.element has its window open and has at least one open window child, hence the path bw them connects 'em";
// cout<<"\n3.else the node must have at least two open window nodes rooted @ itself";
while(*it1 != V+1) //for root of each tree in the forest do the following
{
llu x = *it1 ; //first element of the present tree
llu root_id = r2[x]; //no. of open window nodes rooted @ node x
while( x < *it2 ) //for each element of the tree rooted at it1 do the following
{
if(r2[x] > 0 && r2[x] < root_id) //element has at least 1 open window child also there is some open window node rooted at the same root at which the element is hence at least the way between these 2 nodes connects 'em
{rubik++;} //cout<<"\t 1. "< 1) //element has its window open and has at least one open window child, hence the path bw them connects 'em
{rubik++;} //cout<<"\t 2. "< (V+1, false);
track = vector (V+1, 0);
int i = 0;
while(count(begin(track), end(track), 1)<2 && i < g[it].size()) //loop till either we find at least 2 open window children rooted at concerned node 'x' (lying in remaining) or we visit all adj nodes of x
{
track.pb(dfs_fun(g, it, key, vs));
i++;
}
if(count(begin(track), end(track), 1)>=2) {rubik++;} //cout<<"\n"<