1197 - The Suspects

[mahade hasan]

Acc

[brianfry713]

why why WAA plz help me

Try input:

Code: Select all

2 1
2 0 1
2 1
2 0 1
0 0

[Muftee_Ruet]

Simple DFS problem.

Run DFS from node 0 to find out how many nodes are connected with node 0.
Aware of input : m can be 0.

Happy coding.

[vellvisher]

I am getting RE continuously..

Code: Select all

#include<iostream>
#include<vector>
using namespace std;
typedef vector<int> vi;
class UnionFind{
private: vi p;

public: UnionFind(int N) { p.assign(N+1,-1);}
void reset(int N) { p.clear(); p.assign(N+1, -1);}
int findSet(int i) {if (p[i] < 0) return i; else return p[i] = findSet(p[i]);}
void unionSet(int i, int j) { int x = findSet(i), y = findSet(j); if(p[x] < p[y]) {
        p[x] += p[y];p[y] = x; } else {p[y] += p[x];p[x] = y;}}};
UnionFind uf(1);

int main() {
    int n, m;
    cin >> n >> m;
   while(n) {
       uf.reset(n);
      for(int i = 0; i < m; i++) {
          int k, r,s;
          cin >> k;
          if(k) {
          cin >> r;
        for(int i = 1; i < k; i++) {
            cin >> s;
            if(r+1 > n || s+1 > n) continue;
            uf.unionSet(r+1, s+1);
        }
          }
      }
      int count = 0;
      for(int i = 1; i <= n; i++) {
            count+= uf.findSet(i) == uf.findSet(1);
      }
      cout << count << endl;
      cin >> n >> m;
   }
  return 0;
}

[brianfry713]

http://www.algorithmist.com/index.php/Union_Find

[vellvisher]

Oops..had forgot one case...saw it in the link..thanks a lot!

V

[raiyan21]

I am getting WA. I tried hard to find the bug. But I failed. Here is my code.

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
 
#define INF_MAX 1147483647
#define INF_MIN -1147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i <= (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, (s), sizeof (a))

using namespace std;
map<int,int> pset;
int findSet(int n)
{
	if(n==pset[n])
		return n;
	return (pset[n]= findSet(pset[n]));
}
void merge(int i, int j)
{
	pset[findSet(i)] = findSet(j);
}
int sizeOfSet(int n)
{
	int r = findSet(n);
	int t, cnt = 0;;
	map<int, int>:: iterator it;
	for(it= pset.begin(); it!=pset.end(); it++)
	{
		t = it->second;
		if(t==r) cnt ++;
	}
	return cnt;
}
int main()
{
    int i,j,k,n,m,u,v;
	set<int> node;
	set<int>:: iterator it;
	bool done[30000];
    while(scanf("%d %d", &n, &m) && (n||m))
	{
		/*for(it=node.begin(); it!=node.end(); it++)
		{
			i = *it;
			adj[i].clear();
		}*/
		//For(i,0,504)
			//adj[i].clear();
		Set(done, false);
		pset.clear();
		if(m==0) {
			printf("1\n");
			continue;
		}
		vector<int> temp;
		//node.clear();
		For(i,1,m)
		{
			cin >> u;
			temp.clear();
			For(j,0,u-1)
			{
				cin >> v;
				if(done[v]==false){
					pset[v] = v;
					done[v] = true;
				}
				temp.push_back(v);
			}
			int p,q;
			p = temp[0];
			For(k,1,temp.size()-1)
			{
				q = temp[k];
				merge(p,q);
			}
		}
		
		int ans = sizeOfSet(0);
		cout << ans << endl;
	}
    
    return 0;
}

It will be a great help if anyone give some sample test case so that I can find the bug. Thanx.

[brianfry713]

Why is pset a map and not an array?

[light1k5]

Below is my implementation to keep track of the size of each tree in the disjoint set forest.

Can you please tell me what is wrong with it ? I am trying to solve UVa problem https://goo.gl/ZiQCyH

Code: Select all

#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;

class Node {
    public :
    int id;
    Node *parent;
    unsigned long long rank;



    Node(int id) {
        this->id = id;
       // this->data = data;
        this->rank =1; //size here
        this->parent = this;
    }
    friend class DisjointSet;
};

  class DisjointSet {
    unordered_map<int,Node*> nodesMap;

    Node *find_set_helper(Node *aNode) {

        if (aNode == aNode->parent) {
            return aNode->parent;
        }
        return find_set_helper(aNode->parent);
    }

    void link(Node *xNode,Node *yNode) {
        if( xNode->rank > yNode->rank) {
            yNode->parent = xNode;
            xNode->rank += yNode->rank;
        }
        // else if(xNode-> rank < yNode->rank){
        //     xNode->parent = yNode;
        //     yNode->rank += xNode->rank;
        // }
        else {
            xNode->parent = yNode;
            yNode->rank += xNode->rank;
        }
    }
public:
    DisjointSet() {

    }

    void AddElements(int sz) {
        for(int i=0;i<sz;i++)
            this->make_set(i);
    }

    void make_set(int id) {
        Node *aNode = new Node(id);
        this->nodesMap.insert(make_pair(id,aNode));
    }

    void Union(int xId, int yId) {
        Node *xNode = find_set(xId);
        Node *yNode = find_set(yId);

        if(xNode && yNode)
          link(xNode,yNode);
    }

    Node* find_set(int id) {
      unordered_map<int,Node*> :: iterator itr = this->nodesMap.find(id);
      if(itr == this->nodesMap.end())
          return NULL;

      return this->find_set_helper(itr->second);
    }



    ~DisjointSet(){
        unordered_map<int,Node*>::iterator itr;
        for(itr = nodesMap.begin(); itr != nodesMap.end(); itr++) {
            delete (itr->second);
        }
    }

};
int main() {

    int n,m,k,first,cur;

    //freopen("in.in","r",stdin);

    scanf("%d %d",&n,&m);

    while(n != 0 || m != 0) {

        DisjointSet *ds = new DisjointSet();
        ds->AddElements(n); // 0 to n-1

        //printf("\n n = %d m = %d",n,m);


        for(int i=1;i<=m;i++) {
            scanf("%d",&k);
            //printf("\nk=%d",k);
            if ( k > 0 ) {

                scanf("%d",&first);
                for(int j=2;j<=k;j++) {
                    scanf("%d",&cur);
                    ds->Union(first,cur);
                }
            }
        }

        Node *zeroSet = ds->find_set(0);
       // unsigned long long count = ds->getCount(zeroSet->id);
        printf("%llu\n",zeroSet->rank);
        delete ds;

        scanf("%d %d",&n,&m);
    }

    return 0;
}

The link function in the above code does the job of updating the tree size.

The solution to the problem is to find the set which elements 0 belongs to and get the size of the representative element of the set. But I am getting wrong answer with this code.

Can you please help me