dimanche 30 mai 2021

This DSU problem of UVA is giving WA verdict. I don't get why. Can anyone help it?

Here's the problem link. https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&category=0&problem=3638&mosmsg=Submission+received+with+ID+26446583

For each of m groups, I made union of all of the students in the group. At last, for each student from 0 to n-1 I counted how many of them has parent equals 0. Printed that as result. In union function, I always made the smaller number the parent so that eventually 0 becomes parent.

And it looks obvious to me. But don't know why this code below is givng WA :(

    #include<bits/stdc++.h>
using namespace std;

#define ll long long
int par[30005];

int find(int u) {
  if (u==par[u]) return u;
  return par[u]=find(par[u]);
}

void unionn(int u,int v) {
  int p=find(u);
  int q=find(v);
  if (q<p) swap(q,p);
  if (p!=q) par[q]=p;
}
  

int main() {
  ios_base::sync_with_stdio(0);

  /*freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);*/

  while (1) {
    int n,m; cin>>n>>m;
    if (n==0&&m==0) break;  
    for (int i=0;i<n;i++) par[i]=i;
    while (m--) {
      int k; cin>>k;
      int a[k];
      for (int i=0;i<k;i++) cin>>a[i];
      for (int i=1;i<k;i++) unionn(a[i],a[i-1]);     
    }
    int res=0;
    for (int i=0;i<n;i++) {
      if (par[i]==0) res++;
    }
    cout<<res<<endl;
  }
   

  
  return 0; 
}

 

Aucun commentaire:

Enregistrer un commentaire