# Zurikela's Graph

### Problem Statement :

```Zurikela is creating a graph with a special graph maker. At the begining, it is empty and has no nodes or edges. He can perform 3 types of operations:

1. A x : Create a set of x new nodes and name it set-K.
2. B x y: Create edges between nodes of set-x and set-y.
3. C x : Create a set composed of nodes from set-x and its directly and indirectly connected nodes, called set-K. Note that each node can only exist in one set, so other sets become empty.
The first set's name will be set-1. In first and third operation K is referring to the index of new set:

K = [index of last created set] + 1
Create the graph by completing the Q operations specified during input. Then calculate the maximum number of independent nodes (i.e.:how many nodes in the final graph which don't have direct edge between them).

Input Format

The first line contains Q.
The Q subsequent lines each contain an operation to be performed.

Constraints
.1 <= Q <= 10^5
For the first operation, 1 <= x <= 10^4.
For the second operation, x < y and all ys are distinct.
For the second and third operation, it's guaranteed that set-x and set-y exist.

Output Format

Print maximum number of independent nodes in the final graph (i.e.: nodes which have no direct connection to one another).```

### Solution :

```                            ```Solution in C :

In C++ :

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y)
{ if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y)
{ if(x < y) x = y; }

vector<int> weight;
vector<vi> tree;
vector<int> child;
vector<int> memo;
int K;

int recTree(int i, int p, int j, bool b) {
if(tree[i].size() == j) {
int &r = memo[(K + i) * 2 + b];
if(r != -1) return r;
if(!b) {
return r = 0;
} else if(child[i] == -1) {
return r = weight[i];
} else {
r = 0;
rep(cb, 2)
amax(r, recTree(child[i], -1, 0, cb != 0));
return r;
}
}
int c = tree[i][j];
if(c == p)
return recTree(i, p, j + 1, b);
int &r = memo[c * 2 + b];
if(r != -1) return r;
r = 0;
amax(r, recTree(c, i, 0, false) + recTree(i, p, j + 1, b));
if(!b)
amax(r, recTree(c, i, 0, true) + recTree(i, p, j + 1, b));
return r;
}

void traverse(int x, vi &q, vector<bool> &vis) {
q.clear();
q.push_back(x);
for(int h = 0; h != q.size(); ++ h) {
int i = q[h];
for(int j : tree[i]) if(!vis[j]) {
vis[j] = true;
q.push_back(j);
}
}
}

int main() {
int Q;
while(~scanf("%d", &Q)) {
K = 0;
weight.assign(Q, -1);
tree.assign(Q, vi());
child.assign(Q, -1);
vi q;
vector<bool> vis(Q, false);
for(int ii = 0; ii < Q; ++ ii) {
char ty[10];
scanf("%s", ty);
if(*ty == 'A') {
int x;
scanf("%d", &x);
weight[K] = x;
++ K;
} else if(*ty == 'B') {
int x; int y;
scanf("%d%d", &x, &y), -- x, -- y;
if(!vis[x] && !vis[y]) {
tree[x].push_back(y);
tree[y].push_back(x);
}
} else if(*ty == 'C') {
int x;
scanf("%d", &x), -- x;
traverse(x, q, vis);
child[K] = x;
++ K;
} else abort();
}
memo.assign(K * 4, -1);
int ans = 0;
rep(i, K) if(!vis[i]) {
traverse(i, q, vis);
int x = 0;
rep(b, 2)
amax(x, recTree(i, -1, 0, b != 0));
ans += x;
}
printf("%d\n", ans);
}
return 0;
}

In Java :

import java.io.*;
import java.math.*;
import java.util.*;

public class CodeSprint6_2 {
static class Node{
int val;
boolean active;
int parent;
int ansTake;
int ansNotTake;
ArrayList<Integer> next;
public Node(){
next=new ArrayList<>();
}
}
static int[] val;
static boolean[] active;
static int[] parent;
static int n;
static int ansTake[];
static int ansNotTake[];
static ArrayList<Integer> next[];
static Node[] v;
public static void main(String ars[]) {
Scanner in = new Scanner(System.in);
int q=in.nextInt();
in.nextLine();
n=0;
v=new Node[q];
for(int i=0;i<q;i++){
v[i]=new Node();
}
for(int t=0;t<q;t++){
String[] input = in.nextLine().split(" ");
if(input[0].equals("A")){
v[n].val=Integer.parseInt(input[1]);
v[n].next=new ArrayList<>();
v[n].active=true;
v[n].parent=-1;
n++;
}
if(input[0].equals("B")){
int x=Integer.parseInt(input[1])-1;
int y=Integer.parseInt(input[2])-1;
if(v[x].active && v[y].active){
v[y].parent=x;
}
}
if(input[0].equals("C")){
int z=Integer.parseInt(input[1])-1;
while(v[z].parent!=-1)
z=v[z].parent;
v[n].val=ans;
v[n].next=new ArrayList<>();
v[n].active=true;
v[n].parent=-1;
n++;
}
}
for(int i=0;i<n;i++){
if(v[i].active){
int z=i;
while(v[z].parent!=-1)
z=v[z].parent;
}
}
}

int[] duet = new int[2];
duet[0]=0;
duet[1]=v[z].val;

for(int x:v[z].next){
duet[1]+=temp[0];
duet[0]+=temp[1];
}
duet[1]=Math.max(duet[0], duet[1]);
v[z].active=false;
return duet;
}

}

In C :

#include <stdio.h>
#include <stdlib.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
void insert_edge(int x,int y,int w);
void dfs(int x,int y);
int max(int x,int y);
char str[2];
int a[100000],dp1[2][100000],track[100000]={0};
lnode *table[100000]={0};

int main(){
int Q,x,y,c=0;
scanf("%d",&Q);
while(Q--){
scanf("%s",str);
switch(str[0]){
case 'A':
scanf("%d",&x);
a[c++]=x;
break;
case 'B':
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
break;
default:
scanf("%d",&x);
dfs(x-1,-1);
a[c++]=max(dp1[0][x-1],dp1[1][x-1]);
}
}
for(x=y=0;x<c;x++)
if(!track[x]){
dfs(x,-1);
y+=max(dp1[0][x],dp1[1][x]);
}
printf("%d",y);
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs(int x,int y){
lnode *p;
track[x]=1;
for(p=table[x];p;p=p->next)
if(p->x!=y)
dfs(p->x,x);
dp1[1][x]=0;
dp1[0][x]=a[x];
for(p=table[x];p;p=p->next)
if(p->x!=y){
dp1[0][x]+=dp1[1][p->x];
if(dp1[0][p->x]>dp1[1][p->x])
dp1[1][x]+=dp1[0][p->x];
else
dp1[1][x]+=dp1[1][p->x];
}
return;
}
int max(int x,int y){
return (x>y)?x:y;
}

In Python3 :

from itertools import repeat
M = 200010
AdjList = [[] for i in repeat(None, M)];
dppp = [0 for i in range(M)];
dpp1 = [0 for i in range(M)];
my_str = ""
done = [0 for i in range(M)];
max_ind = [0 for i in range(M)];
N = 0;

dpp1[node] = max_ind[node];
dfs(v, node);
dppp[node] = dppp[node] + max(dppp[v], dpp1[v]);
dpp1[node] = dpp1[node] + dppp[v];
done[node] = 0;

Q = int(input());

for q in range(Q):
my_str = str(input());
u = my_str.split(' ');
if(my_str[0] == 'A'):
x = int(u[1]);
N = N + 1;
max_ind[N] = x;
done[N] = 1;
elif my_str[0] == 'B':
x = int(u[1]);
y = int(u[2]);
elif my_str[0] == 'C':
x = int(u[1]);
dfs(x, x);
N = N + 1;
max_ind[N] = max(dppp[x], dpp1[x]);
done[N] = 1;
ans = 0;
for i in range(N):
if done[i + 1] == 1 :
dfs(i + 1, i + 1);
ans = ans + max(dppp[i + 1], dpp1[i + 1]);
print(str(ans));```
```

## Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing