Cerinta completa

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 types of operations:

  1. : Create a set of new nodes and name it –.
  2. : Create edges between nodes of – and –.
  3. : Create a set composed of nodes from – and its directly and indirectly connected nodes, called –. Note that each node can only exist in one set, so other sets become empty.

The first ‘s name will be –. In first and third operation is referring to the index of new set:

K = [index of last created set] + 1

Create the graph by completing the 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 .
The subsequent lines each contain an operation to be performed.

Constraints
.
For the first operation, .
For the second operation, and all s are distinct.
For the second and third operation, it’s guaranteed that – and – exist.

Output Format

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

Sample Input

8
A 1
A 2
B 1 2
C 1
A 2
A 3
B 3 4
B 4 5

Sample Output

5

Explanation

There are operations.

After first operation:

After second operation:

After third operation:

After fourth operation:

After fifth and sixth operation and :

After seventh operation:

After eigth operation:

There are independent nodes in – and independent nodes in –, so we print their sum () as our answer.

Limbajul de programare folosit: cpp

Cod:

#include <bits/stdc++.h>

using namespace std;

int N;
int A[100001];
vector<int> adj[100001];
bool seen[100001];
int dp[100001][2];

void solve(int u, int p)
{
    seen[u]=true;
    dp[u][0]=0;
    dp[u][1]=A[u];
    for(auto& v: adj[u]) if(v!=p)
    {
        solve(v, u);
        dp[u][0]+=max(dp[v][0], dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}

int main()
{
    scanf("%d", &N);
    char op;
    int a, b;
    int M=1;
    for(int i=0; i<N; i++)
    {
        scanf(" %c", &op);
        if(op=='A')
        {
            scanf("%d", &a);
            A[M++]=a;
        }
        else if(op=='B')
        {
            scanf("%d%d", &a, &b);
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        else if(op=='C')
        {
            scanf("%d", &a);
            solve(a, a);
            A[M++]=max(dp[a][0], dp[a][1]);
        }
    }
    int ans=0;
    for(int i=1; i<M; i++) if(!seen[i])
    {
        solve(i, i);
        ans+=max(dp[i][0], dp[i][1]);
    }
    printf("%d\n", ans);
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464645595

Link challenge: https://www.hackerrank.com/challenges/zurikela/problem

Zurikela’s Graph