3 types

/*
                                               3 types of road  different  for men and women
 Let's consider some weird country with N cities and M bidirectional roads of 3 types. It's weird because of some unusual rules about using these roads: men can use roads of types 1 and 3 only and women can use roads of types 2 and 3only. Please answer the following very interesting question: what is maximum number of roads it's possible to destroy that the country will be still connected for both men and women? Connected country is country where it's possible to travel from any city to any other using existing roads.
Input
The first line contains 2 space-separated integer: N and M. Each of the following M lines contain description of one edge: three different space-separated integers: a, b and c. a and b are different and from 1 to N each and denote numbers of vertices that are connected by this edge. c denotes type of this edge.
Output
For each test case output one integer - maximal number of roads it's possible to destroy or -1 if the country is not connected initially for both men and women.
Constraints
1 <= N <= 1000
1 <= M <= 10 000
1 <= a, b <= N
1 <= c <= 3

Sample Input
 5 7
1 2 3
2 3 3
3 4 3
5 3 2
5 4 1
5 2 2
1 5 1
 ANS-2
****************************EDITORIAL**************]

   short explanation 
  case1-> initiall check graph is conected for men and women or not in the initial phase 
  case 2->first add node of type  3 for men if not  cover all nodes from node of type 1 for men 
        first add node of type  3 for women if not  cover all nodes from node of type 1 for women

detailed explanation 
This problem can be solved with greedy approach.

Let's look at this problem in a different way - instead of deleting as much edges as possible, we'll try to pick as few as possible (and remove everything else).

We have graph for men and graph for women. Let's call them M-graph and W-graph. Obviously there is no need to add edge which doesn't connect something in any of graphs. Therefore any edge we take will connect two components in W-graph, or in M-graph, or in both (this is possible only for edges of 3rd type). You need to make 2N-2 merges (N-1 in W-graph and N-1 in M-graph). As we noticed, every edge will do either 1 merge or 2 merges (as we said before, if can make 2 merges only if it is edge of type 3 and it merges two components in both W-graph and M-graph at the same time). This leads us to a simple greedy: let's pick as many edges doing 2 merges as possible.

Add all edges of 3rd type which are merging distinct components. This can be done using DSU. Now you can actually find answer already - if you have used K edges of 3rd type, you made 2K merges already, and you'll need 2N-2-2K more merges, and it will take 1 edge per merge now. If you have a task to print edges, not only their number - it can be done by solving M-graph and W-graph in similar way, but starting with our partially connected by edges of 3rd type graphs instead of empty one.

And don't forget to check that original M-graph and W-graph are connected. Solution without this check will give you only 90 points.
 */
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int myrank[100010];
int parent[100010];
 int mark[1010][1010];
 int visited[10000000];

typedef long long int lli;
#include<bits/stdc++.h>
 list<pair<int,int > > li[100000];
lli read_int(){
 char r;bool start=false,neg=false;lli ret=0;
 while(true){r=getchar();if((r-'0'<0 || r-'0'>9) && r!='-' && !start){ continue;}
 if((r-'0'<0 || r-'0'>9) && r!='-' && start){ break;}if(start)ret*=10;
start=true;if(r=='-')neg=true;else ret+=r-'0';}if(!neg) return ret;else return -ret;}
int par[1000000];
int ra[10000000];
lli dfs(int t1)
{
              
  
                          stack<lli> s;
 long long int  start= 1;
   s.push(start);
visited[start]=1;
    lli cov=0;
    while(!s.empty())
     {
       lli start=s.top();
         cov++;
             s.pop();
                list<pair<int,int> > :: iterator it;
                for(it=li[start].begin();it!=li[start].end();it++)
                 {
                   if(visited[it->first]!=1  && (it->second==t1 || it->second==3))
                    {
                    visited[it->first]=1;
                    s.push(it->first);
                    }
                 } 
     }
  
  return cov;
   
}
lli find(lli node)
{
     if(parent[node]==node)
     {
   return node;
     }
     else
     find(parent[node]);
}
lli merge(lli a, lli  b)
{
  lli x=find(a);
  lli  y=find(b);
  if(myrank[x]>myrank[y])
  {
      parent[y]=x;
   
  }
  else
  {
      parent[x]=y;
   if(myrank[x]==myrank[y])
   myrank[y]++;
  }
}

lli findi(lli node)
{
     if(par[node]==node)
     {
   return node;
     }
     else
     findi(par[node]);
}
lli mergei(lli a, lli  b)
{
  lli x=findi(a);
  lli  y=findi(b);
  if(ra[x]>ra[y])
  {
      par[y]=x;
   
  }
  else
  {
      par[x]=y;
   if(ra[x]==ra[y])
   ra[y]++;
  }
}


int main()
{
int t;
   
 lli n,m;
n=read_int();
m=read_int();
 vector<pair<pair<lli ,lli >,lli> > vw,vm;
  

 for(lli i=0;i<m;i++)
 {
  lli a , b,c;
     a=read_int();
     b=read_int();
     c=read_int();
     li[a].push_back(make_pair(b,c));
     li[b].push_back(make_pair(a,c));
   if(c==2)
  vw.push_back(make_pair(make_pair(c,a),b) );
  if(c==1)
  vm.push_back(make_pair(make_pair(c,a),b) );
   if(c==3)
    {
     vm.push_back(make_pair(make_pair(c,a),b) );
     vw.push_back(make_pair(make_pair(c,a),b) );
    }
 }
 for(lli i=1;i<=n;i++)
 {
    parent[i]=i;
    par[i]=i;
 }
    memset(visited,0,sizeof visited);
int cov1=dfs(1);
memset(visited,0,sizeof visited);
int cov2=dfs(2);
    if(cov1!=n ||  cov2!=n)
     {
       cout<<"-1"<<endl;
       return 0;
     }

 sort(vm.begin(),vm.end());
 reverse(vm.begin(),vm.end());
 sort(vw.begin(),vw.end());
 reverse(vw.begin(),vw.end());

lli cov=0;
 long long int cost=1;
 for(lli i=0;i<vm.size();i++)
 {
     lli a,b,c;
        a=vm[i].first.second;
        b=vm[i].second;
        c=vm[i].first.first;
       if(find(a)!=find(b))
       {
                    if(mark[a][b]!=1)
                    {
                     cov++;
                          mark[a][b]=1;
                    }
              merge(a,b);
       }
 }
 for(lli i=0;i<vw.size();i++)
 {
     lli a,b,c;
        a=vw[i].first.second;
        b=vw[i].second;
        c=vw[i].first.first;
           
       if(findi(a)!=findi(b))
       {
                    if(mark[a][b]!=1)
                    {
                     cov++;
                          mark[a][b]=1;
                    }
                mergei(a,b);
       }
 }
 cout<<m-cov<<endl;


 return 0;
}

                                 Coal Scam

Chef has entered the politics of Byteland. He is a minister in the coal department of the government. Recently, he has been assigned a project on constructing special bidirectional roads for transferring coals in such a way that the whole country is connected by a road network.

Different companies submitted their proposal of roads that they could build along with their estimated cost of the road. Chef has to select a subset of these proposed roads so that all cities of the country are connected.

Chef, corrupt as he is, managed to submit bids by his own company for certain roads. If some of his proposed roads are selected, he'd use low grade material. We can safely assume that the cost of building these roads is nothing to him. He would still receive the price he has quoted in the bid and hence, would make as much profit. He wants to choose some subset of proposed roads so that his own profit is maximised.

Byteland consists of N cities. There are M1 proposals to build roads by companies other than Chef's. Chef's company has proposed to build M2 roads. Chef wants to choose a subset of these roads in such a way that for each pair of cities, there is exactly one path of roads connecting them. The profit Chef will gain is equal to the sum of costs of the roads chosen from among those made by Chef's company.

Help Chef choose the roads in such a way that his profit is maximized. If there are multiple ways to achieve that, choose the way where the sum of costs of all chosen roads is minimized.

Input

The first line of the input contains a number T, the number of test cases. This is followed by the input for each test case one by one. The first line of each test case contains three space-separated integers N, M1, and M2. Then M1 lines follow, each containing a description of a road proposed by other companies. Each of these lines contains three space-separated integers u, v, and c, where u and v denote the end points of the road and c denotes the associated cost. Then M2 lines follow, each containing a description of a road proposed by Chef's company in the same format.

Output

Output a single line for each test case. If it is impossible to choose a subset of the roads in such a way that for each pair of cities, there is exactly one path of roads connecting them, output a single line containing "Impossible" (quotes for clarity and starts with an uppercase 'I') for that test case. Otherwise, output a single line containing two space-separated integers: the maximum profit Chef can gain and the minimum total cost of the chosen roads that yields the maximum profit.

Example

Input:
2
3 2 1
0 1 5
1 2 4
0 1 10
3 1 1
0 1 1
0 1 3

Output:
10 14
Impossible

Constraints

1 ≤ T ≤ 5
2 ≤ N ≤ 5,000
1 ≤ M1 ≤ 20,000
1 ≤ M2 ≤ 20,000
For each proposed road, the end points will be two different cities.
There may be several proposed roads between the same pair of cities.
For each proposed road, 0 ≤ c ≤ 1,000,000,000

Each input file will not be larger than 4 MB (4,000,000,000 bytes) in size.

---------------------------------------EDITORIAL---------------

THIS IS A SIMPLE MST PROBLEM ONLY DIFFERENCE IS THAT SOME OF THE EDGE IS FIXED  .. AND WE NEED TO USE UNION FIND TO DECIDE REST REMAINING EDGES OF MST..

first connect all nodes which are given by minister .. also first sort all input  in decreasing order of cost of minister  since minister want to make more money so it will construct more cost node ..now  try to connect nodes 1 by 1 using union find also maintain a graph of selected node and edge so that latter we can check that is there any disconnected graph .. after that 

now   take input of other builders and sort them and in this case try to connect low cost edge(incresing order of cost ) first soo use in incresing sorted order  also maintain graph if any new node added (if found by union find that it can be connect )..

 finally ans will be 

apply bfs on constructed graph if visit all nodes than  

 benifit of minister = cost in first part  , and total cost = ans of first +second part 

else answer=IMPOSSIBLE 

==========================CODE======================================

#include<iostream>

#include<stdio.h>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long int lli;

lli rank[1000100];

lli par[1000100];

#include<bits/stdc++.h>

lli  find(lli a)

  {

    if(par[a]!=par[par[a]])

     {

      par[a]=find(par[a]);

     }

     return par[a];

 }

lli merge(lli a, lli  b)

{

  lli x=find(a);

  lli y=find(b);

  if(rank[x]>rank[y])

  {

      par[y]=x;

   

  }

  else

  {

      par[x]=y;

   if(rank[x]==rank[y])

   rank[y]++;

  }

}

int main()

{

int t;

cin>>t;

 while(t--)

  {

   

    lli n,m1,m2;

    list<lli> li[10000+100];

     cin>>n>>m1>>m2;

      int visited[100000];

      for(lli i=0;i<=n+10000;i++)

              {

                   par[i]=i;

                   visited[i]=0;

                   rank[i]=0;

                  }

   

          lli c , a,b;

     

         

          vector<pair<pair<lli,lli>, lli > > v;

          

       for(lli i=0;i<m1;i++)

        {

          cin>>a>>b>>c;

          v.push_back(make_pair(make_pair(c,a),b));

        }

        

         sort(v.begin(),v .end());

         lli cc= 0,pub=0;

          //cout<<"reading chef "<<endl;

         

         vector<pair<pair<lli,lli>, lli > > v2;

        for(lli i=0;i<m2;i++)

        {

         cin>>a>>b>>c;

          v2.push_back(make_pair(make_pair(c,a),b));

        }

        

         sort(v2.begin(),v2.end());

         reverse(v2.begin(),v2.end());

     for(lli i=0;i<m2;i++)

      {

     

       a=v2[i].first.second;

       b=v2[i].second;

       c=v2[i].first.first;

       if(find(a)!=find(b))

        {

          cc+=c;

          merge(a,b);

          li[a].push_back(b);

          li[b].push_back(a);

          

        }

       

     

      }

       

        for(int i=0;i<m1;i++)

      {

     

       a=v[i].first.second;

       b=v[i].second;

       c=v[i].first.first;

       if(find(a)!=find(b))

        {

          pub+=c;

          merge(a,b);

          li[a].push_back(b);

          li[b].push_back(a);

          

        }

       

     

      }

       

         

            lli count=0;

            

             stack<lli>s;

              s.push(0);

                visited[0]=1;

              while(!s.empty())

               {

                lli start=s.top();

                s.pop();

                 

                   count++;

                     list<lli> :: iterator it;

                      for(it=li[start].begin();it!=li[start].end();it++)

                       {

                        if(!visited[*it])

                         {

                          visited[*it]=1;

                           s.push(*it);

                         }

                       }

               }

       //    cout<<" count is "<<count<<endl;

            if(count==n)

            cout<<cc<<" "<<cc+pub<<endl;

            else

               cout<<"Impossible"<<endl;

              // for(int i=0;i<n;i++) cout<<par[i]<<" "<<i<<endl;*/

  }

 

 return 0;

}

DSU TOPCODER - CONCEPT

By  vlad_D– TopCoder Member
Discuss this article in the forums

Introduction
Many times the efficiency of an algorithm depends on the data structures used in the algorithm. A wise choice in the structure you use in solving a problem can reduce the time of execution, the time to implement the algorithm and the amount of memory used. During SRM competitions we are limited to a time limit of 2 seconds and 64 MB of memory, so the right data structure can help you remain in competition. While someData Structures have been covered before, in this article we’ll focus on data structures for disjoint sets.

The problem
Let’s consider the following problem: In a room are N persons, and we will define two persons are friends if they are directly or indirectly friends. If A is a friend with B, and B is a friend with C, then A is a friend of C too. A group of friends is a group of persons where any two persons in the group are friends. Given the list of persons that are directly friends find the number of groups of friends and the number of persons in each group. For example N = 5 and the list of friends is: 1-2, 5-4, and 5-1. Here is the figure of the graph that represents the groups of friends. 1 and 2 are friends, then 5 and 4 are friends, and then 5 and 1 are friends, but 1 is friend with 2; therefore 5 and 2 are friends, etc.

In the end there are 2 groups of friends: one group is {1, 2, 4, 5}, the other is {3}.

The solution
This problem can be solved using BFS, but let’s see how to solve this kind of problem using data structures for disjoint sets. First of all: a disjoint-set data structure is a structure that maintains a collection S1, S2, S3, …, Sn of dynamic disjoint sets. Two sets are disjoint if their intersection is null. For example set {1, 2, 3} and set {1, 5, 6} aren’t disjoint because they have in common {1}, but the sets {1, 2, 3} and {5, 6} are disjoint because their intersection is null. In a data structure of disjoint sets every set contains a representative, which is one member of the set.

Let’s see how things will work with sets for the example of the problem. The groups will be represented by sets, and the representative of each group is the person with the biggest index. At the beginning there are 5 groups (sets): {1}, {2}, {3}, {4}, {5}. Nobody is anybody’s friend and everyone is the representative of his or her own group.

The next step is that 1 and 2 become friends, this means the group containing 1 and the group with 2 will become one group. This will give us these groups: {1, 2} , {3}, {4}, {5}, and the representative of the first group will become 2. Next, 5 and 4 become friends. The groups will be {1,2}, {3}, {4, 5}. And in the last step 5 and 1 become friends and the groups will be {1, 2, 4, 5}, {3}. The representative of the first group will be 5 and the representative for second group will be 3. (We will see why we need representatives later). At the end we have 2 sets, the first set with 4 elements and the second with one, and this is the answer for the problem example: 2 groups, 1 group of 4 and one group of one.

Perhaps now you are wondering how you can check if 2 persons are in the same group. This is where the use of the representative elements comes in. Let’s say we want to check if 3 and 2 are in the same group, we will know this if the representative of the set that contains 3 is the same as the representative of the set that contains 2. One representative is 5 and the other one is 3; therefore 3 and 2 aren’t in same groups of friends.

Some operations
Let’s define the following operations:

• CREATE-SET(x) – creates a new set with one element {x}.
• MERGE-SETS(x, y) – merge into one set the set that contains element x and the set that contains element y (x and y are in different sets). The original sets will be destroyed.
• FIND-SET(x) – returns the representative or a pointer to the representative of the set that contains element x.

The solution using these operations
Let’s see the solution for our problem using these operations:

Read N;
for (each person x from 1 to N) CREATE-SET(x)
for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)

Now if we want to see if 2 persons (x, y) are in same group we check if FIND-SET(x) == FIND-SET(y).

We will analyze the running time of the disjoint-set data structure in terms of N and M, where N is the number of times that CREATE-SET(x) is called and M is the total number of times that CREATE-SET(x), MERGE-SETS(x, y) and FIND-SET(x) are called. Since the sets are disjoint, each time MERGE-SETS(x, y) is called one set will be created and two will be destroyed, giving us one less set. If there are n sets after n-1 calls of MERGE-SETS(x,y) there will remain only one set. That’s why the number of MERGE-SETS(x,y) calls is less than or equal to the number of CREATE-SET(x) operations.

Implementation with linked lists
One way to implement disjoint set data structures is to represent each set by a linked list. Each element (object) will be in a linked list and will contain a pointer to the next element in the set and another pointer to the representative of the set. Here is a figure of how the example of the problem will look like after all operations are made. The blue arrows are the pointers to the representatives and the black arrows are the pointers to the next element in the sets. Representing sets with linked lists we will obtain a complexity of O(1) for CREATE-SET(x) and FIND-SET(x). CREATE-SET(x) will just create a new linked list whose only element (object) is x, the operation FIND-SET(x) just returns the pointer to the representative of the set that contains element (object) x.

Now let’s see how to implement the MERGE-SETS(x, y) operations. The easy way is to append x’s list onto the end of y’s list. The representative of the new set is the representative of the original set that contained y. We must update the pointer to the representative for each element (object) originally on x’s list, which takes linear time in terms of the length of x’s list. It’s easy to prove that, in the worst case, the complexity of the algorithm will be O(M^2) where M is the number of operations MERGE-SETS(x, y). With this implementation the complexity will average O(N) per operation where N represents the number of elements in all sets.

The “weighted union heuristic”
Let’s see how a heuristic will make the algorithm more efficient. The heuristic is called “a weighted-union heuristic.” In this case, let’s say that the representative of a set contains information about how many objects (elements) are in that set as well. The optimization is to always append the smaller list onto the longer and, in case of ties, append arbitrarily. This will bring the complexity of the algorithm to O(M + NlogN) where M is the number of operations (FIND-SET, MERGE-SETS, CREATE-SETS) and N is the number of operations CREATE-SETS. I will not prove why the complexity is this, but if you are interested you can find the proof in the resources mentioned at the end of the article.

So far we reach an algorithm to solve the problem in O(M + NlogN) where N is the number of persons and M is the number of friendships and a memory of O(N). Still the BFS will solve the problem in O(M + N) and memory of O(N + M). We can see that we have optimized the memory but not the execution time.

Next step: root trees
The next step is to see what we can do for a faster implementation of disjoint set data structures. Let’s represent sets by rooted trees, with each node containing one element and each tree representing one set. Each element will point only to its parent and the root of each tree is the representative of that set and its own parent. Let’s see, in steps, how the trees will look for the example from the problem above.

Step 1: nobody is anybody friend

We have 5 trees and each tree has a single element, which is the root and the representative of that tree.

Step 2: 1 and 2 are friends, MERGE-SETS(1, 2):

The operation made is MERGE-SETS(1, 2). We have 4 trees one tree contain 2 elements and have the root 1. The other trees have a single element.

Step 3: 5 and 4 are friends, MERGE-SETS(5, 4)

The operation made is MERGE-SETS(5, 4). Now we have 3 trees, 2 trees with 2 elements and one tree with one element.

Step 4: 5 and 1 are friends, MERGE-SETS(5, 1)

The operation made is MERGE-SETS(5, 1). Now we have 2 trees, one tree has 4 elements and the other one has only one element.

As we see so far the algorithm using rooted trees is no faster than the algorithm using linked lists.

Two heuristics
Next we will see how, by using two heuristics, we will achieve the asymptotically fastest disjoint set data structure known so far, which is almost linear in terms of the number of operations made. These two heuristics are called “union by rank” and “path compression.” The idea in the first heuristic “union by rank” is to make the root of the tree with fewer nodes point to the root of the tree with more nodes. For each node, we maintain a rank that approximates the logarithm of the sub-tree size and is also an upper bound on the height of the node. When MERGE-SETS(x, y) is called, the root with smaller rank is made to point to the root with larger rank. The idea in the second heuristic “path compression,” which is used for operation FIND-SET(x), is to make each node on the find path point directly to the root. This will not change any ranks.

To implement a disjoint set forest with these heuristics, we must keep track of ranks. With each node x, we keep the integer value rank[x], which is bigger than or equal to the number of edges in the longest path between node x and a sub-leaf. When CREATE-SET(x) is called the initial rank[x] will be 0. When a MERGE-SETS(x, y) operation is made then the root of higher rank will become the parent of the root of lower rank – or, in case of tie, we arbitrarily choose one of the roots as the parent and increment its rank.

Let’s see how the algorithm will look.

Let P[x] = the parent of node x.
CREATE-SET(x) 
 P[x] = x
 rank[x] = 0
MERGE-SETS(x, y)
 PX = FIND-SET(X)
 PY =FIND-SET(Y)
 If (rank[PX] > rank[PY]) P[PY] = PX
 Else P[PX] = PY
 If (rank[PX] == rank[PY]) rank[PY] = rank[PY] + 1

And the last operation looks like:

FIND-SET(x) 
 If (x != P[x]) p[x] = FIND-SET(P[X])
 Return P[X]

Now let’s see how the heuristics helped the running time. If we use only the first heuristic “union by rank” then we will get the same running time we achieved with the weighted union heuristic when we used lists for representation. When we use both “union by rank” and “path compression,” the worst running time is O( m α(m,n)), where α(m,n) is the very slowly growing inverse of Ackermann’s function. In application α(m,n) <= 4 that’s why we can say that the running time is linear in terms of m, in practical situations. (For more details on Ackermann’s function or complexity see the references below.)

Back to the problem
The problem from the beginning of the article is solvable in O(N + M) and O(N) for memory using disjoint-set data structure. The difference for time execution is not big if the problem is solved with BFS, but we don’t need to keep in memory the vertices of the graph. Let’s see if the problem was like: In a room are N persons and you had to handle Q queries. A query is of the form “x y 1,” meaning that x is friends with y, or “x y 2” meaning that we are asked to output if x and y are in same group of friends at that moment in time. In this case the solution with disjoint-set data structure is the fastest, giving a complexity of O(N + Q).

Practice
Disjoint-set data structures are a helpful tool for use in different algorithms, or even for solving problems in an SRM. They are efficient and use small amount of memory. They are useful in applications like “Computing the shorelines of a terrain,” “Classifying a set of atoms into molecules or fragments,” “Connected component labeling in image analysis,” and others.

To practice what you’ve learned, try to solve GrafixMask – the Division 1 500 from SRM211. The idea is to keep track of all the blocks and consider each grid point as a node. Next, take all the nodes that aren’t blocked and let (x, y) be the coordinate of the left, right, down or up node, and if (x, y) is not blocked then you do the operation MERGE-SETS(node, node2). You should also try to determine how disjoint-set data structures can be used in the solution of RoadReconstruction from SRM 356. Disjoint-set data structures can also be used inTopographicalImage from SRM 210 and PathFinding, from SRM 156.

I hope you find this data structure to be useful. Good luck in the Arena!

References:

• Thomas H. Cormen, Introduction to Algorithms
• en.wikipedia.org/wiki/Disjoint-set_data_structure
• en.wikipedia.org/wiki/Ackermann_function