ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1160. Network

WA6
Posted by SProf 16 Feb 2016 17:19
i try to solve it with kruskal and it gives me wa6 can anyone help me?
Re: WA6
Posted by c_pp 11 Jan 2017 01:38

struct edge
{
   int len; int a; int b;
};

int rank[1024];
int parent[1024];
edge e[15008];
int n,m;
int get_parent(int x)
{
   if (x != parent[x])parent[x] = get_parent(parent[x]);
   return parent[x];
}

bool join_dsu(int x, int y){
      x = get_parent(x); y = get_parent(y);
     if (x == y) return false;
    if (rank[x] < rank[y]) parent[x] = y; else if (rank[x] > rank[y]) parent[y] = x;
    else parent[y] = x, ++rank[x];
  return true;
}

//  read edges
//  sort edges by len
//  p[i] = i, for i = 1..n
//  let l_min = 0;
//   i = 1..m
//   if (  join_dsu( e[i].a, e[i].b) ){ l_min = e[i].len; }
//  print l_min   and all edges where len <= l_min,  GOOD LUCK !!